[백준/C++] 2805번: 나무 자르기 - 이분 탐색과 매개변수 탐색

1. 문제 정보

• 문제 번호: 2805번
• 문제 이름: 나무 자르기
• 문제 요약: 절단기에 높이 H를 지정하면 H보다 높은 나무의 윗부분을 가져갈 수 있다. 적어도 M미터의 나무를 가져가기 위해 설정할 수 있는 절단기 높이의 최댓값을 구하라.

2. 왜 이분 탐색인가? (시간 복잡도의 마법)

이 문제에서 절단기의 높이는 0부터 가장 높은 나무의 높이(최대 10억)까지 가능합니다.

• 선형 탐색: 0부터 10억까지 하나씩 높여가며 확인한다면? 최악의 경우 10억 번의 연산이 필요합니다. 나무의 개수 N이 100만 개이므로, 전체 연산량은 10^9 X10^6 = 10^{15}... 절대 시간 내에 통과할 수 없습니다.
• 이분 탐색: 탐색 범위를 반씩 줄여나가면 log_2(10^9) = 30번의 연산만으로 충분합니다. 나무가 100만 개여도 30 X 1,000,000 = 3,000만번 정도의 연산으로 끝나기 때문에 아주 여유롭게 통과할 수 있죠!

 

3. 핵심 개념: 매개변수 탐색 (Parametric Search)

매개변수 탐색은 '최적화 문제'를 '결정 문제'로 바꾸어 푸는 기법입니다.

• 최적화 문제: "가져갈 수 있는 나무가 M 이상이 되는 절단기 높이의 최댓값은?"
• 결정 문제: "절단기 높이를 X로 설정했을 때, 가져가는 나무의 합이 M 이상인가? (Yes/No)"

이분 탐색을 진행하면서 "Yes"라면 높이를 더 높여보고, "No"라면 높이를 낮추는 과정을 반복하며 최적의 값을 찾아냅니다.

 

 

4. 구현 디테일 (주의할 점)

① long long 자료형 선택

나무의 개수가 최대 100만 개이고, 각 나무의 높이가 최대 10억입니다. 절단기를 낮게 잡으면 잘린 나무들의 합(sum)이 int 범위(약 21억)를 훌쩍 넘길 수 있습니다. 따라서 sum 변수는 반드시 long long으로 선언해야 합니다.

② max_element 활용

이분 탐색의 시작 범위(low)는 0, 끝 범위(high)는 나무 중 가장 높은 나무의 높이입니다. 이때 *max_element(v.begin(), v.end())를 사용하면 벡터 내의 최댓값을 쉽게 찾을 수 있습니다.

 

5. 코드 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long M;
    cin >> N >> M;

    vector<int> trees(N);
    for (int i = 0; i < N; i++) {
        cin >> trees[i];
    }

    // 이분 탐색의 범위 설정
    long long low = 0;
    long long high = *max_element(trees.begin(), trees.end());
    long long result = 0;

    while (low <= high) {
        long long mid = (low + high) / 2;
        long long sum = 0;

        // 현재 높이(mid)로 나무를 잘랐을 때 얻는 합 계산
        for (int i = 0; i < N; i++) {
            if (trees[i] > mid) {
                sum += (trees[i] - mid);
            }
        }

        // 결정 문제: 합이 M 이상인가?
        if (sum >= M) {
            result = mid; // 일단 기록 (더 높은 높이가 있을 수 있음)
            low = mid + 1; // 더 높여본다
        } else {
            high = mid - 1; // 너무 많이 잘라야 함, 높이를 낮춘다
        }
    }

    cout << result << "\n";

    return 0;
}

 

6. 배운 점 & 회고 (TIL) ✍️

① 탐색 범위가 크면 이분 탐색을 의심하라

단순 반복문으로 풀었을 때 시간 초과가 날 것 같다면, 탐색 대상이 정렬되어 있거나(이 문제에서는 높이 0~10억), 조건에 따라 탐색 범위를 반으로 쪼갤 수 있는지 확인하는 습관을 들여야겠습니다.

② 데이터 타입의 중요성

알고리즘이 맞더라도 자료형 하나 때문에 틀릴 수 있다는 것을 다시 느꼈습니다. 문제 조건에서 "값의 합"이나 "곱"이 나오면 무조건 범위를 체크하는 습관이 중요합니다.

③ 매개변수 탐색의 위력

단순히 "값"을 찾는 이분 탐색을 넘어, "조건을 만족하는 최적의 값"을 찾는 매개변수 탐색의 개념을 확실히 잡았습니다. 이 기법은 공유기 설치(2110번)나 랜선 자르기(1654번) 같은 고난도 문제에서도 똑같이 쓰인다고 하니 잘 익혀둬야겠습니다.