[BOJ] 2805 나무자르기

문제 링크 :

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

몸이 안 좋아도 블로그는 정상 영업합니다……..

매개 변수 탐색(=파라메트릭 서치, Parametric Search) 문제이다.

Parametric Search란?

최적화 문제를 결정 문제로 바꾸어 푸는 것

최적화 문제: 조건을 만족하는 어떤 변수의 최솟값 또는 최댓값을 구하는 문제

이런 최적화 문제를 결정 문제로 바꾸어 푸는 것이 parametric search이다.

예를들면, 2805 나무자르기 문제에서 이진탐색을 하면서 mid만큼의 높이로 잘랐을 때, 그 잘린 나무 길이의 합이 필요한 나무 길이를 충족시켜주는지 결정해주는 함수를 만들면 된다.

bool can_make(ll M, ll mid) {
    ll total = 0;
    for(int h: height) {
        if(h >= mid) total += h-mid;
    }

    if(total >= M) return true;
    else return false;
}

can_make의 반환 값이 true → 톱의 높이를 좀 더 올려서 그 때에도 조건이 충족되는지 확인한다. 즉, mid값을 저장해놓고 left = mid+1로 바꾸어 이진 탐색을 계속한다.

can_make의 반환 값이 false → 톱의 높이를 낮추어야한다. right = mid -1로 바꾸어 이진탐색을 계속한다.

입력이

4 7

20 15 10 17

일 때

이진탐색의 범위를 left = 0, right = (최대 나무 길이)로 했기 때문에 처음 mid 값은 (20+0) / 2 = 10이다.

톱 위치가 10일 때, 잘리는 나무의 길이는 그림과 같이 22이므로, 7보다 커서 조건을 충족한다.

그럼 톱의 위치를 올려서 이 조건을 충족하면서 더 큰 값이 있는지 찾아야한다.

따라서 left = mid+1로 바꾼다.

left = 11이 되었으므로, 두 번째 mid는 (11+20)/2 = 15이다.

톱 높이가 15일 때, 잘리는 나무 길이는 그림과 같이 7이므로 조건을 충족하고, 15가 정답이다.

다음 반복 때 left = 16, right = 20인 상태로 이진탐색이 더 진행되겠지만, 앞으로는 결정해주는 함수가 fasle만 리턴할 것이고, right의 값이 작아지다가 left>right가 되면서 반복문이 종료될 것이다.

정리하자면

can_make의 리턴값에 의해 범위를 좁혀가며 이진탐색을 계속하면, 조건을 만족하면서 톱 높이의 최댓값을 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
vector<ll> height;

bool can_make(ll M, ll mid) {
    ll total = 0;
    for(int h: height) {
        if(h >= mid) total += h-mid;
    }

    if(total >= M) return true;
    else return false;
}

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

    int N;
    ll M;

    cin >> N >> M;

    for(int i=0; i<N; ++i) {
        ll tmp;
        cin >> tmp;
        height.push_back(tmp);
    }

    ll left = 0;
    ll right = (ll)(*max_element(height.begin(), height.end()));
    ll ans = 0;
    while(left <= right) {
        ll mid = (left + right) / 2;

        if(can_make(M, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

참고

처음에 ‘틀렸습니다’가 떠서 당황했는데, 알고보니 톱 위치가 0이 될 수도 있다는 것을 까먹고 left = 1로 이진탐색을 시작해서 그랬던거였다..

ans도 -1로 초기화했었고 left도 1로 시작했었는데, 이렇게되면

3 3

1 1 1

과 같은 테케를 넣으면 정답 값 0 대신에 -1(ans의 초기화값)이 출력된다.

left = 0으로 시작하면 해결된다. (아니면 ans = 0으로 초기화해도 해결된다.)