📌 [BOJ] 백준 2805 나무 자르기

📖 문제

📖 예제

📖 풀이

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

start = 0
end = max(tree)

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

print(result)

나무를 어느 높이에서 자를 것인지에 대해 이분 탐색을 수행하면 된다.
나무의 길이가 mid로 설정한 자르는 높이보다 클 경우 길이 - mid를 모든 나무에 대해 더해준 후 그 값을 필요로 하는 길이 M과 비교한다.