[boj 1114] 통나무 자르기

www.acmicpc.net/problem/1114

 

 

 알고리즘 : 이분탐색(파라메트릭) + 그리디

 

몇주 전 풀고 올려야지! 하고 생각만 하다 이제야 올리는 문제다.

처음에 문제 분류가 그리디 + 이분탐색으로 되있어서 난 그리디 못하니까 이분탐색만 써서 풀어야지 했다가

여러번 삽질하고서야 둘다 써야 된다는걸 알았다.

 

이분 탐색으로 일단, 최대로 자르는 통나무의 길이가 x일때 조건에따라 자르는게 가능한지 아닌지를 찾아준다.

왜 이런식으로 잡는지, 파라메트릭으로 왜 되는지 다시 한 번 집고 넘어가자면

f(x) : 최대 통나무의 길이를 x로 잡을때, 조건에 따라 자르는 것이 가능하다 (boolean 값 return)

 

라고 하면, x의 증가에 따라 f(x)의 값이 ... 0 0 0 0 0 0 1 1 1 1 1 1.......(계속1)

꼴, 즉 f(x)의 형태가 monotonic increasing(decreasing한 경우에도 가능하다.)이기 때문이다.

이떄 이분 탐색을 통해서 f(x)가 1을 만족하는 가장 작은 x의 값을 찾아주면 된다.

 

자르는 통나무의 길이를 고정시켜놨으므로, 이제 자르는 통나무의 길이가 주어질 때, 이걸 가지고 가장 효율적으로(자르는 것이 가능한쪽으로) 그리디하게 짜면 된다.

어떤식으로 그리디하게 짜면 되냐??

통나무의 각 자르는 위치를 통나무의 오른쪽부터 보면서, 지금 자르는 부분까지 봣을때는, 최대 길이 x이하임을 만족하면서, 다음 부분(더왼쪽 부분)에서 자를 떄는 길이 x를 넘어버릴때에만, 자르는 것으로 하면 된다.

(이 때, 자르는 것이 불가능한 경우가 생기는 것도 잘 처리해 주면 된다.)

 

마지막으로, 이 부분을 처리 안해서 계속 틀렷었는데

이 과정을 거치고도 자를 수 있는 횟수가 남아있으면, 처음위치에서 무조건 자를 수 있으므로

    if (cnt > 0) {

        fc = min(fc, v[0]);

    }

를 통해 통나무를 자르는 위치를 갱신시켜주면된다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e9;
typedef pair<int, int> pi;
int n, k, c;
vector<int>v;
int fc = (int)2e9;
bool ispos(int len) {// 최대 길이가 len일떄 가능하냐?
    int lc = n;
    int cnt = c; // cut 가능횟수
    for (int i = k - 1; i >= 0; i--) {
        int nx = (i == 0 ? 0 : v[i - 1]);
        if (lc - v[i] > len)return 0;
        if (lc - nx > len) {
            if (cnt == 0)return 0;
            lc = v[i];
            cnt--;
        }
    }
    if (lc > len)return 0;
    return 1;
}
bool ispos2(int len) {// 최대 길이가 len일떄 가능하냐?
    int lc = n;
    int cnt = c; // cut 가능횟수
    for (int i = k - 1; i >= 0; i--) {
        int nx = (i == 0 ? 0 : v[i - 1]);
        if (lc - v[i] > len)return 0;
        if (lc - nx > len) {
            if (cnt == 0)return 0;
            lc = v[i];
            fc = min(fc, lc);
            cnt--;
        }
    }
    if (cnt > 0) {
        fc = min(fc, v[0]);
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> c;
    v.resize(k);
    for (int& i : v)cin >> i;
    sort(v.begin(), v.end());
    ll lo = 0, hi = 2e9;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (ispos(mid))hi = mid;
        else lo = mid + 1;
    }
    ispos2(lo);// fc 갱신
    cout << lo << " " << fc;
}