백준 2805번 :: 나무 자르기 (python)

문제

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

분류 

• 이분탐색
• 매개변수 탐색

나의 풀이

n,m = map(int,input().split())

tree = list(map(int,input().split()))
lt=0
rt=max(tree)
tree.sort()
while lt<=rt:
    mid=(lt+rt)//2
    cnt =0
    for x in tree:
        if x> mid:
            cnt+=x-mid
    if cnt >= m:
        lt = mid+1
    else:
        rt = mid-1
print(rt)

이 문제를 살짝 헤맸던 이유가

오른쪽 (rt)변수에 n-1을 했었다

그렇게 해서 풀면 예시1번은 풀리지만 2번에서 답이 안나온다

 

이러한 문제는 rt에 값을 넣어서 푸는 문제로 들어가면 이진탐색 문제를 쉽게 풀 수 있다 

 

절단기 높이의 최대값을 찾는 문제이기 때문에 오른쪽(rt) 변수에 max(나무 값) 해주면 된다