나무 자르기 - 2805번

이분탐색으로 해결해야 시간초과가 안생기는 문제이다.

 

처음에 나무 최대 길이에서 1씩 줄여가면서 답에 근접할 때 멈추는 방식으로 풀었었는데 역시나 시간초과가 발생했다.

 

이분탐색을 이용하여 나무 최대길이를 high, 최소길이인 0을 low로 둔다.

무한루프를 통해 중간길이를 계산하며 나무가 잘린 길이를 계산해준다.

만약, 나무가 잘린 길이가 너무 많다면 low = mid로 해주고, 나무를 덜 잘랐다면 high = mid를 해준다. 

나무를 자를 길이는 양의 정수로만 계산되므로 무한루프의 종료지점을 high - low > 1로 해준다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
l = list(map(int, input().split()))

high = max(l)
low = 0
while high-low > 1:
    mid = (high+low)//2
    tree_dead = 0

    for i in l:
        if i > mid:
            tree_dead+=i-mid

    if tree_dead >= m:
        # print('td, m', tree_dead, mid)
        low = mid
    else:
        # print('td, m', tree_dead, mid)
        high = mid
print(low)