[python] 백준 2805 번 : 나무 자르기 (실버 2)

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

해당 문제에서 발생할 수 있는 문제는 시간 초과와 이를 해결할 이진탐색이다.

n , m = map(int,input().split())
trees = list(map(int,input().split()))
hightree = max(trees)
result = 0
low , high = 0 , max(trees) ### low에 m-1 이 아닌 0을 넣어야 함
while low <= high:
    mid = (low+high)//2 # 이진 탐색으로 해야 시간을 줄일수가 있음
    total = 0
    for tree in trees:
        if tree > mid :
            total += tree - mid

    if total >= m: # 원하는 값보다 크면 전기톱 길이를 늘려야 더 적게 나오므로 low의 값을 높여준다.
        result = mid
        low = mid + 1 
    else:   # 원하는 값보다 작으면 전기톱 길이를 짧게 해야 하므로 high 값을 더 낮게 해준다.
        high = mid - 1
print(result)