[백준 2805] 나무 자르기(Python)

1. 아이디어

문제에서 원하는 것은 적어도 M미터의 나무를 가져가기 위해, 절단기에서 설정할 수 최대 높이다. 따라서 이분 탐색을 통해 찾아야 하는 값은 절단기의 높이다. 절단기의 높이는 최소 1부터 설정할 수 있으므로, left는 1로 설정한다. 그리고 right는 주어진 나무들 중 높이가 가장 높은 것으로 설정한다. 이후 각 나무의 높이에 대해 mid(절단기의 높이)를 차감하고, 그 결과를 합산한다. 합산한 결과가 M이상이고 최대 값인지 확인한다.

잘라서 획득한 나무의 높이가 M이상이면, 절단기의 높이가 낮아서 나무를 많이 자른 것을 의미하므로, 절단기의 높이를 높여준다.(i.e. left = mid + 1) 반면, 잘라서 획득한 나무의 높이가 M미만이면 절단기의 높이가 너무 높아서 나무를 적게 자른 것을 의미하므로, 절단기의 높이를 낮춘다.(i.e. right = mid - 1)

2. 코드

import sys

n, m = map(int, sys.stdin.readline().rsplit())
trees = list(map(int, sys.stdin.readline().rsplit()))
left, right = 1, max(trees)
answer = 0
while left <= right:
    mid = (left + right) // 2
    total = 0
    for tree in trees:
        remain = tree - mid
        if remain > 0: total += remain

    if total >= m:
        left = mid + 1
        answer = max(answer, mid)

    else: right = mid - 1

print(answer)