[백준] 나무 자르기_2805

가장 맨 처음 풀어봤었던 파라메트릭 서치 문제. 여기서는 "x 또는 그보다 좋은 답이 존재하는가?" 이 질문에 검사하는 내용이 딱 한 줄이다.

if (sum < M) right = mid - 1;

else {

    if (ans < mid) ans = mid;

    left = mid + 1;

}

저 if문 부분... 근데 if (sum >= M) 으로 했어야 좀 더 파라메트릭 서치의 의미에 가까울 것 같다. 

 

또, 이 문제였는지는 기억이 잘 안 나지만 다른 문제에서 틀렸던, 주의해야 할 부분은 제일 초기에, 답이 존재하는 부분을 잘 잡아야 한다는 것이다. left=1로 잡아서 틀렸었던 기억이 난다. 

종만북에서는 이것을 이분법의 함정 - 수치적 안정성을 잃어버릴 수 있다고 표현했다. 고정된 수의 후보만을 탐색하기 때문에 잘못하면 오차가 생길 수 있다. 

#include <iostream>
using namespace std;
 
long long N, M;
long long t[1000000];
int ans = 0;
 
int main() {
    cin >> N >> M; 
    int left = 0, right = 0;
    for (int i = 0; i < N; i++) {
        cin >> t[i];
        if (right < t[i]) right = t[i];
    }
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long sum = 0; 
        for (int i = 0; i < N; i++) {
            if (t[i] > mid) sum += t[i] - mid;
        }
        if (sum < M) right = mid - 1;
        else {
            if (ans < mid) ans = mid;
            left = mid + 1;
        }
    }
    cout << ans;
    return 0;
}