[백준] 2805 나무 자르기 - C++

 매개 변수 탐색 문제(Parametric Search)는 그냥 이분 탐색 문제와는 접근방법이 조금 다르다. 기본적인 이분탐색 문제의 경우에는 배열 요소들을 정렬해준 뒤, 위치를 찾아내기만 하면 된다.

 하지만 2805번 문제와 같이 매개 변수 탐색 문제 같은 경우에는 조건을 만족하는 최소/최댓값을 구하는 문제, 즉 최적화 문제를 결정 문제로 변환해 이분탐색으로 문제를 해결해야 한다. 이걸 모르면 이분 탐색을 사용해서 풀라고해도 모를 수 있다. 나 또한 그랬다... :)

 

 그럼 2805번 문제를 살펴보자. 문제에선 상근이가 M 미터 이상의 나무를 가져가야 하는데, M미터 이상의 나무를 가져가면서 절단기 높이의 최대 길이를 구해야한다. 이제 매개 변수 탐색 문제라고 했으니, '절단기 높이'와 '상근이가 취할 수 있는 나무 길이' 사이의 함수를 구해보자.

 

'절단기 높이'와 '상근이가 취하는 나무 길이'와의 함수

  정확한 함수를 내기는 어렵겠지만, 위의 함수처럼 절단기 높이가 높아지면 높아질수록 상근이가 취할 수 있는 나무길이는 줄어들 것이다. 그렇기에 함수를 보면 단방향 함수인 것을 알 수 있다. 

 만약 중간에 절단기 높이가 높아졌는데 상근이가 취하는 나무 길이가 증가하는 등의 함수가 그려진다면 이 문제는 매개 변수 탐색 및 이분 탐색으로 풀 수 없는 문제이다. 이분 탐색의 기본 조건은 정렬되어 있는 배열이 전제조건이기 때문!! 이제 코드를 짜는 것은 간단하다. 절단기 높이를 start, mid, end 변수를 두고 기존에 이분탐색 문제처럼 풀면 되는 것이다. 

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N, M;
int namu[1000005];

// 상근이가 취한 나무 길이가 M 미터 이상인지 체크하는 함수
bool solve(ll x) {
    ll cur = 0;
    for (int i = 0; i < N; i++) {
        if (namu[i] > x) {
            cur += namu[i] - x;
        }
    }
    return cur >= M;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> namu[i];
    }
    ll st = 0;
    ll en = 2100000000;

    ll ans = 0;
    while (st <= en) {
        ll mid = (st + en) / 2;
        if (solve(mid)) {
            st = mid + 1;
            ans = max(ans, mid);
        }
        else en = mid - 1;
    }
    cout << ans;
}