BOJ 2805 - 나무 자르기 (C++) / Parametric Search

https://www.acmicpc.net/problem/2805

문제를 푼 날짜: 2025. 06. 04

#binary_search #parametric_search

Parametric Search란?

(https://ialy1595.github.io/post/parametric-search/ 의 내용을 참고하였습니다.)

• Parametric Search는 최댓값/최솟값을 구하는 최적화 문제를,
  "어떤 값 x가 조건을 만족하는가?"라는 결정문제로 바꾼 뒤,
  Binary Search를 이용해 답을 빠르게 찾는 문제 해결 기법이다.
• 실생활에서 정확한 값을 한 번에 구하지 않고 "이 정도면 되나?"를 반복해서 조금씩 조정하며 원하는 값을 찾는 식(예: 저울에 고기를 여러 번 올리며 200g 맞추기)의 사고라고 생각할 수 있다.
• 파라메트릭 서치를 쓸 수 있으려면,

1. 최댓값/최솟값을 구하는 문제여야 하고,
2. 조건을 만족하는 값들의 구간이 연속적이어야 하며,
3. 답의 범위가 이산적이거나(정수), 허용 오차가 있어야 한다.

아이디어

이 문제는 "최댓값을 구하는 문제"이고, 그 값을 직접 계산하기엔 복잡하다. 따라서 조건을 만족하는지 확인하는 결정 문제로 바꾼 후, 이분 탐색을 이용하는 Parametric Search 기법을 사용한다.

✔️ H 높이로 잘랐을 때, 나무 길이의 합이 M 이상인가?를 판단하는 결정 문제로 변형하고
✔️ 만족한다면 더 높이 자를 수 있는지 탐색
✔️ 만족하지 못한다면 톱 높이를 낮추는 방향으로 탐색

내 코드 (C++)

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

using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<int> trees(N);

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

    int low = 0, high = 1000000000;
    int ans;

    while(low <= high){
        int mid = (low + high) / 2;

        ll sum = 0;
        for(auto &tree: trees){
            sum += max(0, tree - mid);
        }

        // 높이를 mid로 설정했을 때 요건을 만족 -> 정답 후보로 저장하고, 높이를 올리기
        if(sum >= M) {
            ans = mid;
            low = mid + 1;
        }

        // 요건 만족 x -> 높이를 낮춰봄
        else high = mid - 1;
    }

    cout << ans;
    return 0;
}

분석

• 시간복잡도: $O(N logH)$ -> $H$는 나무의 최대 높이인 $10^9$.
  -> 시간 내에 충분히 들어옴!
• 처음에 sum을 int형으로 선언해서 WA가 떴고, 원인을 찾지 못했음.
  -> sum은 $10^6 \times 10^9 = 10^{15}$으로 int 범위 충분히 초과 가능!
  -> 항상 변수의 범위에 유의할 것
• 톱 높이는 최소 0부터, 최대는 문제에 주어진 나무 높이의 최댓값(= $10^9$)까지 가능하다.
  → 따라서 low = 0, high = 1,000,000,000으로 탐색 범위를 설정한다.
  -> 최댓값을 $10^9$ 대신 입력된 나무 중 제일 높은 나무의 높이로 잡아도 된다. (조금 더 최적화된 코드)