⌛ 2805번 나무 자르기

📌 문제

2805번 나무 자르기

📝 코드

이분 탐색의 대표적인 문제 중 하나다.
이 문제를 통해서 이분 탐색 문제를 어떻게 풀어야 할지 알게 되었다.

아래처럼 코드를 작성하면 PyPy3에서는 통과가 되는데, Python3에서는 시간 초과가 발생한다.

n, m = map(int, input().split())
tree_list = list(map(int, input().split()))

left = 0
right = max(tree_list)
result = []
while left <= right:
  mid = (left + right) // 2
  count = 0
  for tree in tree_list:
    if tree >= mid:
      count += tree - mid

  if count == m:
    result.append(mid)
    break
  elif count > m:
    result.append(mid)
    left = mid + 1
  else:
    right = mid - 1

print(max(result))

자른 나무 길이의 합을 구하는 방식을 아래처럼 바꿔주면 Python3에서도 통과가 가능하다.

n, m = map(int, input().split())
tree_list = list(map(int, input().split()))

left = 0
right = max(tree_list)
result = []
while left <= right:
  mid = (left + right) // 2
  count = 0
  count = sum(tree - mid if tree >= mid else 0 for tree in tree_list)

  if count == m:
    result.append(mid)
    break
  elif count > m:
    result.append(mid)
    left = mid + 1
  else:
    right = mid - 1

print(max(result))