[Python] 백준 2805 - 나무자르기

백준 2805 - 나무자르기

문제

코드

import sys

input = sys.stdin.readline


def binary():
    global mid, start, end, pre_mid, s
    while start <= end:
        s= 0
        mid = (start + end) // 2
        for i in range(N):
            if tree[i] > mid:
                s += tree[i] - mid

        if s == M:
            pre_mid = mid
            return
        elif s > M:
            pre_mid = mid
            start = mid + 1
        else:
            end = mid - 1


N, M = list(map(int, input().split()))
tree = list(map(int, input().split()))

end = max(tree)
start = 0
mid = 0
s = 0
pre_mid = 0

binary()

print(pre_mid)

해설

1. 이분탐색을 이용하여 값을 찾아내었다.
2. 원하는 나무길이와 정확하게 일치하는 값이 나오지 않을 수도 있다. 따라서 자른 나무길이의 합이 원하는 값 보다 클 경우, pre_mid에 mid값을 저장해준 다음 이후에 길이의 합이 모두 원하는 값보다 작을 때에 pre_mid 를 출력할 수 있도 록 하였다.
3. 정확하게 값이 일치할 때와 아닐 때를 굳이 나눌 필요 없다고 생각해 s==m일 때에도 pre_mid = mid를 해주었다.