[백준/Python] 2805번 나무 자르기 - 파라메트릭 서치(Parametric Search) 완벽 체화

학습 철학 회고
단순히 주어진 배열에서 숫자를 찾는 것을 넘어, "적어도 M미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값"을 구하는 최적화 문제를 만났습니다. 이를 해결하기 위해 이분 탐색을 응용한 '파라메트릭 서치(Parametric Search)'의 뼈대를 설계하고, 탐색 공간을 재정의하는 과정을 거쳤습니다.

📌 문제 요약: 2805번 나무 자르기

나무의 수 $N$은 최대 100만, 가져가야 하는 나무의 길이 $M$은 최대 20억입니다. 톱의 높이를 1씩 줄여가며 선형 탐색($O(N \times \text{max\_height})$)을 하면 무조건 시간 초과가 발생합니다.
따라서 "높이를 $H$로 설정했을 때, 얻을 수 있는 나무가 $M$ 이상인가? (Yes/No)"라는 결정 문제로 바꾸어 $O(N \log (\text{max\_height}))$ 시간 복잡도로 해결해야 합니다.

💻 실전 조립 코드 (SOP 적용)

import sys

input = sys.stdin.readline

def binary_search_parametric(N, M, trees):
    # 1. 탐색 공간 설정: 배열의 인덱스가 아니라 '톱의 설정 높이' 범위!
    left = 0
    right = max(trees)
    best_answer = -1

    # 2. 이분 탐색 진행
    while left <= right:
        mid = (left + right) // 2
        
        # 3. 결정 함수(Yes/No) 통과 여부 확인
        if check_condition(trees, mid) >= M: 
            best_answer = mid # 조건을 만족하므로 일단 안전망에 저장 (Checkpoint)
            left = mid + 1    # "더 톱을 높게 설정해도 M미터가 나오는지 욕심내보자!"
        else:
            right = mid - 1   # 잘린 나무가 부족하므로 톱의 높이를 낮춰야 함
            
    return best_answer

def check_condition(trees, target_height):
    # [최적화] sum()과 제너레이터 표현식을 활용하여 O(N) 연산을 단 1줄로 압축
    # 나무가 톱의 높이(target_height)보다 클 때만 잘라서 더함
    return sum(tree - target_height for tree in trees if tree > target_height)

def solution():
    N, M = map(int, input().split())
    trees = list(map(int, input().split()))
    
    print(binary_search_parametric(N, M, trees))

if __name__ == "__main__":
    solution()

🚨 트러블 슈팅 및 심화 회고

파라메트릭 서치의 뼈대를 세우며 겪었던 3가지 핵심 고민을 기록합니다.

1. 탐색 공간(Search Space)의 착각
처음에는 left = 0, right = N - 1로 설정하여 '배열의 인덱스'를 탐색하려고 했습니다. 하지만 톱의 높이는 배열 안에 존재하는 나무의 높이와 정확히 일치하지 않을 수 있습니다. 따라서 탐색 공간 자체를 '톱이 가질 수 있는 높이의 범위 (0부터 가장 높은 나무까지)'로 재설정해야 완벽한 시뮬레이션이 가능함을 깨달았습니다.

2. 왜 == M으로 찾지 않고 부등호(>= M)를 쓰는가?
정확히 $M$미터로 떨어지는 톱의 높이가 존재하지 않을 수 있습니다. 문제의 요구사항은 '적어도 $M$미터'이므로, $M$미터 이상을 만족하는 조건 안에서 최댓값을 찾아야 합니다. 따라서 부등호는 필수불가결한 요소입니다.

3. check_condition의 음수 예외 처리
톱의 높이보다 낮은 나무는 잘리지 않아야 합니다. 처음에 조건문 없이 tree - height를 모두 더했다가, 잘리지 않은 나무가 오히려 전체 길이를 깎아먹는 논리적 오류를 발견했습니다. 이를 파이썬의 조건부 제너레이터 if tree > target_height를 통해 아주 깔끔하고 파이썬답게 방어했습니다.