[Beakjoon] 1114 통나무 자르기 (C++)

문제 링크

BOJ 1114 : 통나무 자르기

문제

풀이

우선순위 큐를 이용해서 현재 유지하고 있는 가장 긴 통나무를 자르는 것을 처음 생각해봤다.

이 문제에서는 통나무를 자를 수 있는 위치가 지정되어 있고, 가장 긴 통나무를 기준으로 자른다고 할 때,
1. 해당 통나무에 자를 수 있는 위치가 있는가
2. 일정 횟수가 정해져있는데, 특정 시점에서 가장 긴 것을 자르는 게 최선인가
를 생각해봤을 때 잘못된 풀이인 것을 알 수 있었다.

이 문제의 경우는 이분탐색을 이용해서 가장 긴 통나무의 길이값을 예상하고 해당 길이로 자르는 것이 가능한지 확인하는 과정을 통해 해결한다.

골치아팠던 것은 처음으로 자르는 통나무의 위치도 출력해야한다는 것이었다.

결정된 가장 긴 통나무 길이의 최소값을 answer이라고 할 때,

처음 자르는 위치는 다음과 같다.
1. answer길이로 자르고도 자를 수 있는 횟수가 남는 경우 -> 가장 처음에 있는 지점
2. answer 길이로 뒤에서부터 잘랐을 때 마지막으로 자르는 지점

2번이 생각하기 힘들었다.
answer길이로 자르더라도 원래 통나무의 길이가 answer로 나누어 떨어지지 않으면, 분명 answer보다 작은 길이의 통나무가 존재할 것이다. 앞에서부터 자르는 경우는 가장 작은 통나무가 앞에 있을 거란 사실을 배제하고 경우를 탐색하기 때문에 뒤에서부터 확인해서 마지막으로 자르는 지점을 출력한다.

예외처리를 해야하는 부분이 있어서 까다로웠다.. 정답률 낮은 문제는 풀기 두렵다.

코드

    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <limits.h>

    #define endl "\n"

    using namespace std;

    int L,K,C;
    vector<int> V;
    int check(int l){

        int len, befo, now, cnt;
        len = 0; befo = 0; cnt = C;
        for(int i=0; i<V.size(); i++){
            now = V[i];

            if(now-befo>l) return -1;

            if(len+(now-befo)<=l){
                len+=(now-befo);
            }
            else{
                len = (now-befo);
                cnt--;
                if(cnt<0) return -1;
            }
            befo = now;
        }

        return cnt;
    }
    void Solve() {
        cin>>L>>K>>C;

        int a;
        for(int i=0; i<K; i++){
            cin>>a;
            V.push_back(a);
        }
        
        sort(V.begin(), V.end());
        V.push_back(L);

        int l,r,m, answer;
        l=1; r=L; answer=INT_MAX;
        while(l<=r){
            m=(l+r)/2;
            if(check(m)>=0) {
                r=m-1;
                answer = min(answer, m);
            }
            else l=m+1;
        }

        cout<<answer<<" ";

        if(check(answer)>0){
            cout<<V[0];
        }
        else{
            int len=0, befo = L, now, cut=V[0]; 
            for(int i=V.size()-1; i>=0; i--){
                now = V[i];
                if(len+(befo-now)==answer){
                    len = 0;
                    cut = now;
                }
                else if(len+(befo-now)>answer){
                    len = (befo-now);
                    cut = befo;
                }
                else {
                    len+=(befo-now);
                }
                befo = now;
            }
            
            cout<<cut;
        }
    }


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

        return 0;
    }