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

이 문제는 이분탐색을 활용하는 문제다.

 

이분탐색을 통해 가장 긴 조각의 최소값을 찾을 수 있다.

 

1~L(통나무전체길이) 까지의 길이 중 검사할 길이를 이분탐색으로 정하고

 

통나무의 가장 긴 조각이 이보다 작은지 검사해서 가장 긴 조각의 최소값을 찾으면 된다.

 

그런데 통나무의 모든 조각이 특정 길이보다 작은지 검사할 수 있는 방법이 생각이 안났다.

 

그래서 아래 질문 글의 코드를 참고하여 그 방법을 알아보았다.

https://www.acmicpc.net/board/view/51740

 

간단하게 말하면 그냥 한쪽끝에서 통나무조각이 검사하는 길이에 최대한 가깝게 자르면 된다.

 

처음에는 잘 이해가 안됐는데 생각보다 간단했다.

 

그림과 같이 길이가 L인 통나무가 있고 통나무의 모든 조각이 S보다 작은지 확인해보자

 

x < S 이고 x+y > S 라면 아래와 같이 길이 x만큼 통나무를 자르면 된다.

 

여기서 자르면 된다.

"길이 x 보다 작게 자르는 것이 더 최적의 방법일 수도 있지 않을까?" 라는 생각이 들 수 있지만 그렇지 않다.

 

x 만큼 자르면 남은 통나무의 길이가 L-x 이지만 x보다 작게 자르면 남은 통나무의 길이가 L-x보다 더 길어진다.

 

남은 통나무 길이는 더 긴데 자를 수 있는 횟수는 같다. 당연히 후자가 작게 자르기 더 불리한 조건이다.

 

따라서 한 쪽 끝부터 검사하는 길이에 가장 가깝게 자르는 것이 최적의 방법이다.

 

이 로직대로면 통나무 조각이 특정 길이보다 작아질 수 있는지 검사할 수 있다.

 

다만 왼쪽부터 자르면 최대한 길게 자르기 때문에 처음 자르는 위치가 왼쪽에서 가장 멀다.

 

반대로 오른쪽부터 자르면 왼쪽에서 가장 가깝게 자르는 위치를 구할 수 있다.

 

위 로직대로 코드를 구현하면 아래와 같다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int L, K, C;
int ks[10001];

int check(int tgt) {

    int temp = 0;
    int from = L;
    int cut = C;
    // 오른쪽부터 탐색
    for(int i = K-1; i>=0 && cut>0; i--) { 
        if(from-ks[i] > tgt) {  // 나무조각이 목표길이보다 커지면 직전 지점에서 자름
            if(ks[i+1]-ks[i] > tgt) {  // 목표길이보다 작게 자를수 없는 조각 발견시 -1 반환
                return -1;
            }
            cut--;
            from = ks[i+1];
        }
    }

    if(cut > 0) {
        from = ks[0];  // 아직 자를 수 있다면 가장 왼쪽에서 자름
    }

    if(from > tgt) {
        return -1;  // 남은 조각이 목표길이보다 크면 -1 반환
    }
    else {
        return from; // 그렇지 않으면 자른 위치중 가장 왼쪽값 반환
    }
}

int main() {

    cin >> L >> K >> C;
    for(int i = 0; i < K; i++) {
        cin >> ks[i];
    }

    sort(ks, ks+K);  //자르는 위치 정렬
    ks[K] = -1;
    int j = 0;
    for(int i = 0; i < K; i++) {  // 자르는 위치 중복값 제거
        ks[j] = ks[i];
        if(ks[i] != ks[i+1]) {
            j++;
        }
    }
    K = j;
    ks[K] = L;

    int start = L/(C+1);
    int end = L;
    int mid, ret;
    while(start<end) {  // L/(C+1)부터L까지 이분탐색
        mid = (start+end)/2;
        ret = check(mid);
        if(ret >= 1) {
            end = mid;
        }
        else{
            start = mid+1;
        }
    }
    
    cout << start << ' ' << check(start) << endl;
    
    return 0;
}

 

알고나니 간단한데 왜 그렇게 생각이 안났는지 모르겠다.