[ BOJ ] 백준 2805 - 나무 자르기(파이썬 문제 풀이)

문제 링크

2805번: 나무 자르기

 

이분 탐색 나무 자르기 문제 입니다.

M미터의 나무의 값을 찾기위해 시작값과 끝값의 범위를 중간값을 기준으로 확장, 축소하며 M미터가 가능한 최소값을 찾았습니다.

 

문제 풀이(파이썬)

---

import sys

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

res = 0
lt = 0
rt = max(tree)
mid = 0
while lt+1<rt:
    mid = (rt+lt) // 2

    res_tmp = 0
    for t in tree:
        if t>mid:
            res_tmp = res_tmp + (t-mid)
            
    if res_tmp == M:
        lt = mid
        break
    elif res_tmp > M:
        lt = mid
    elif res_tmp < M:
        rt = mid
print(lt)