[1일 1백준] 15919 - 사자는 여행왕이야!!

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

15919번: 사자는 여행왕이야!!

여행 사이의 간격을 최소화하는 dp문제인 것 같다만, 솔직히 잘 모르겠다. 안타깝게도 무슨 알고리즘을 이용해야하는지, 문제에 전혀 힌트가 없다. 질문도 아무도 안해서;; 내가 알아서 풀어야할 듯 하다.

 

우선 이 문제의 특이한 점은, "간격"을 최소화하는 것이다. 예를 들어, 8일정도 쉬고 나머지를 전부 꽉채워도, 10일을 1일씩 여행간격마다 쉬는 것이 더 낫다는 것이다. 처음에는, 단순하게 dp[i]가 무엇인지를 정의하고 풀어내려고 했는데, 내 머리로는 풀리지 않아 dp[i]에다가 무언가를 추가하기로 했다.

 

dp[i]를 pair로 활용,

dp[i].first = (dp[i].second에서 끝나는 여행 중 하나를 이용한 스케줄의 최대 간격의 최소치)

dp[i].second = (i 아래로 여행이 끝나는 날 가장 마지막 날짜)

 

그리고 여행이 끝나는 날을 기준으로 여행이 시작하는 날을 vector<vector<int>>에 담기로 했다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

    pair<int, int> dp[1001];
    vector<vector<int>> travels(1001);
    int n, m;
    cin >> n >> m;

    while(m--){
        int start, end;
        cin >> start >> end;
        travels[end].push_back(start);
    }

    dp[0].first = 0;
    dp[0].second = 0;

    int last = 0;
    for(int i = 1; i <= n; i++){
        if(!travels[i].empty()){
            int minimum = 1001;
            for(int start : travels[i]){
                for(int j = 1; j <= start; j++)
                    minimum = min(max(start - dp[j - 1].second - 1, dp[j - 1].first), minimum);
            }
            dp[i].first = minimum;
            dp[i].second = i;
        } else {
            dp[i] = dp[i - 1];
        }
    }

    int minimum = 1001;
    for(int j = 1; j <= n; j++)
        minimum = min(max(n - dp[j - 1].second, dp[j - 1].first), minimum);
    minimum = min(max(n - dp[n].second, dp[n].first), minimum);

    cout << minimum;

    return 0;
}

최종적인 코드는 이렇게 되는데, 대강... O(N * M + 2N) 정도 하는것 같다. 이런 경우에는 시간 복잡도를 따지기도 좀 어렵다. dp[i]에는 단순히 "여행을 했을 때"의 정보만 들어있으므로, 정말로 dp[i]까지의 여행일정을 보았을 때 간격의 최솟값을 따지기 위해서는 1~i까지의 순회하면서 여행을 이용하지 않는 경우의 수까지 포함시켜 계산을 해주어야한다.

 

중간에, 반례고 뭐고 못찾아서 Green55님의 블로그에서 코드를 가져와서 반례를 자동으로 만들어주는 코드로 겨우 풀었다... 아무래도 여기가 통상적으로 해결이 가능한 문제의 한계인듯하다. 그래도, 이번 문제를 풀어서 G3가 된건 나름 기분이 좋기는하다 ㅎㅎ