[백준/2805] 나무 자르기 - 파이썬 Python

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

사용 개념: 이분탐색

 

1. start = 1, end = 나무 최대 높이로 설정하고 절단기 높이(mid)를 조절해 나간다.
2. 벌목된 나무 길이가 M보다 크면 절단기 높이를 올려야 하므로 start = mid + 1으로 조정, M보다 작으면 절단기 높이를 낮춰야 하므로 end = mid - 1으로 조정한다.

import math

n, m=map(int, input().split())
tree=list(map(int, input().split()))
start, end = 1, max(tree)

while start<=end:
    mid = (start+end)//2
    
    log = 0
    for i in tree:
        if i>=mid:
            log += i - mid
    
    if log >= m:
        start = mid + 1        
    else:
        end = mid - 1

print(end)