[백준] 2805 나무 자르기

📌문제 링크

2805 나무 자르기

💡 문제 풀이

원래 이진 탐색의 개념은 정렬된 배열 또는 트리에서 인덱스 범위를 좁혀가며 값을 찾는 거지만, 여기서는 나무의 길이 자체를 인덱스로 활용하여 인덱스가 곧 답이 되는 방식으로 풀었다.

1. 0부터 나무의 최대 길이까지를 이진 탐색의 범위로 설정한다.
(start = 0, end = max(tree))

2. mid = (start + end) // 2 의 높이로 나무를 잘랐을 때 나무의 길이를 계산한다.
(각 나무의 길이에서 mid만큼 뺀 값을 모두 더함)

3. 나무의 길이가 부족한 경우 절단기의 높이를 낮춘다.
(if total < m: end = mid - 1)

4. 나무의 길이가 충분한 경우 절단기의 높이를 높인다.
이 때, 나무의 길이를 m보다 크게 잘랐어도 m만큼은 확보했기 때문에 결과값인 result에 mid 값을 저장한다.
(if total >= m : start = mid + 1, result = mid)

📋코드

import sys
n, m = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(tree)

result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in tree:
        # 잘랐을 때의 나무의 길이 계산
        if x > mid:
            total += x - mid
    # 나무의 길이가 부족한 경우 절단기 높이 낮춤
    if total < m:
        end = mid - 1
    # 나무의 길이가 넘치는 경우 절단기 높이 높임
    else:
        result = mid  # 최대한 덜 잘랐을 때의 길이를 구하기 위해 result에 기록
        start = mid + 1

print(result)