[백준/2805] 나무 자르기

문제 링크: https://www.acmicpc.net/problem/2805

문제 접근

이분 탐색은 범위와 찾을 값을 잡는 것이 중요한 것 같다.

해당 문제의 범위는 전기톱의 높이이며, 찾을 값은 잘라진 나무 높이의 합이 원하는 나무 높이보다 큰 전기톱의 높이 중 최대 값이다.

과정은 다음과 같다.

1. 전기톱 높이의 범위를 설정한다. start: 1, end: 나무의 최대 높이
2. mid: (start + end) // 2 해당 값으로 자른 나무의 총 합을 구한다.
   • 원하는 나무 높이 <= 총 합이면 전기톱의 높이를 더 높게 설정해도 된다는 뜻이다. start: mid + 1
   • 원하는 나무 높이 > 총 합이면 전기톱의 높이를 낮춰야한다는 뜻이다. end: mid - 1
3. 원하는 나무 높이 <= 총 합를 충족하는 전기톱의 높이 중 최대값을 찾음

소스 코드

from typing import List


def cut_and_sum_trees(tree_heights: List[int], cur_height: int):
  return sum(map(lambda x: (x - cur_height) if (x - cur_height) >= 0 else 0, tree_heights))


def binary_search(tree_heights: List[int], target_height: int) -> int:
  max_height = 0

  start = 1
  end = max(tree_heights)

  while start <= end:
    cur_height = (start + end) // 2
    tree_sum = cut_and_sum_trees(tree_heights, cur_height)

    if target_height <= tree_sum:
      max_height = max(max_height, cur_height)
      start = cur_height + 1
    else:
      end = cur_height - 1

  return max_height

  
def input_and_calculate():
  target_height: int = int(input().split(" ")[1])
  tree_heights: List[int] = list(map(int, input().split(" ")))

  return binary_search(tree_heights, target_height)


print(input_and_calculate())