[백준] 1114 - 통나무 자르기

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

1114번: 통나무 자르기

 

이 문제는 처음 보자마자 이분 탐색을 이용한 파라매트릭 서치 문제인 걸 파악했다. 물론 두 번째 출력이 없다면 이분 탐색만으로 가능하다.

하지만 가장 긴 조각의 길이를 가지는 방법의 처음 자르는 위치 때문에 한 가지를 더 살펴보아야 한다.

 

어떻게 하면 가장 작은 처음 자르는 위치를 구할 수 있을까?

 

먼저 통나무의 가장 긴 조각(A)을 정해놓고 생각해보자.

만약 L = 8, K = 3, C = 2이고 각 자르는 위치는 2, 3, 5라고 하자.

 

A = 3일 때, 자를 수 있는 경우의 수는 다음과 같다.

1. [2] [5] 에서 자르기

2. [3] [5] 에서 자르기

 

1번은 뒤에서부터 A이하의 최대 길이로 계속 자른 것이고,

2번은 앞에서부터 A이하의 최대 길이로 계속 자른 것이다.

답은 1번이니 뒤에서부터 A이하의 최대 길이로 자르면 처음 자르는 위치가 가장 작게 자를 수 있다!

 

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int main() {
    int l, k, c;
    cin >> l >> k >> c;
    for (int i = 1; i <= k; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    v.push_back(l);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int left = 1, right = l;
    int ans, ansf; // 통나무의 가장 긴 조각, 그 때의 위치
    while (left <= right) {
        int mid = (left + right) / 2;
        
        // 이전의 자를 위치, 남은 자를 수 있는 횟수
        int prev = l, cnt = c;
        bool flag = true;
        for (int i = v.size() - 1; i >= 0; i--) {
            if (prev - v[i] > mid) { // 이전에 자른 위치와 비교해 크면
                if (v[i + 1] - v[i] > mid) { // 바로 앞의 위치가 mid 보다 크면 자를 수 없다
                    flag = false;
                    break;
                }
                cnt--; // 자른다
                prev = v[i + 1]; 
                if (cnt == 0) {
                    break;
                }
            }
        }
        
        // 자를 수 있는 횟수가 남았으면 최대한 처음 자르는 위치는 작게 해야한다
        if (cnt > 0) {
            prev = v[0]; 
        }
        
        // 처음 자르는 위치가 mid 보다 크면
        if (prev > mid) {
            flag = false;
        }
        
        if (!flag) {
            left = mid + 1;
        } else {
            right = mid - 1;
            ans = mid;
            ansf = prev;
        }
    }
    cout << ans << ' ' << ansf;
}