[BOJ] 2805. 나무 자르기(python)

📌문제

💪아이디어

1. 목재절단기 높이 범위 정하기
   목재 절단기의 높이는 0에서 부터 최대 제일 높은 나무만큼 범위를 잡을 수 있다.
2. 목재절단기 높이 찾기
   나무높이 - h 를 모아 m만큼만 가지고 가기 때문에 최대 h값을 찾아야했다. 시간복잡도로 인해 binary search를 사용했다.
   

🥂코드

n,m = map(int,input().split())
trees = list(map(int,input().split()))
start, end = 0, max(trees)
answer = 0
while start <= end:
    mid = (start + end)//2
    cnt = 0
    for tree in trees:
        if tree > mid: cnt += tree - mid
    
    if cnt < m: end = mid - 1
    else: 
        answer = mid
        start = mid + 1
print(answer)