BOJ 15589 Lifeguards (Silver)

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

15589번: Lifeguards (Silver)

 

다른 시간대에 포함되는 어떤 시간대가 존재한다면, 해당 시간대의 guard 를 해고하면 된다.
서로 포함되지 않는 시간대들만 남게 된다면 DP로 해결할 수 있다.

DP [ 0 ][ i ] : 0 ~ i 번째 guard 들이 커버할 수 있는 시간
DP [ 1 ][ i ] : i ~ n-1 번째 guard 들이 커버할 수 있는 시간

라고 정의하면 

$$answer = max(DP [0][i] + DP[1][i+2])$$

가 된다. 이때, i 번째 guard와 i+2번째 guard의 시간이 겹친다면, 겹치는 만큼 빼주면 된다

해당 풀이가 적용될 수 있는 이유는, i번째 guard 는 i-1번째 guard 보다 늦게 시작하고, 늦게 끝나기 때문이다.

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

using namespace std;

int n, answer, totalLength;
vector<pair<int, int >> point;
vector<pair<int, int >> pointPrimary;

int DP[2][1000000];

int main(){

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    cin >> n;
    point.resize(n);
    for(int i=0;i<n;i++) cin >> point[i].first >> point[i].second;
    
    if(n == 1){
        cout << 0 <<"\n";
        return 0;
    }
    
    sort(point.begin(), point.end());
    int start = -1 , end = -1; //point[0].first, end = point[0].second;
    int beforeLength = 0, idx = 0;
    totalLength = end - start;
    bool in = false;
    //DP[0][idx] = totalLength;
    for(int i=0;i<n;i++){
        //always point[i].first <= point[i].second
        if(point[i].second <= end) in = true;
        else{
            if(point[i].first < end) end = point[i].second;
            else{
                totalLength += (end - start);
                start = point[i].first;
                end   = point[i].second;
            }
            pointPrimary.push_back(point[i]);
            DP[0][idx++] = totalLength + (end - start);
        }
    }
    

    totalLength += (end - start);
    if(in){
        cout << totalLength << "\n";
        return 0;
    }


    int N = idx = pointPrimary.size();
    start = 1000000001, end = 1000000001;
    totalLength = 0;
    for(auto it = pointPrimary.rbegin(); it != pointPrimary.rend(); ++it){
        
        if(end < it->second) end = it->first;
        else{
            totalLength += (start - end);
            start = it->second;
            end = it->first;
        }
        DP[1][--idx] = totalLength + (start - end);
    }
    int answer = max(DP[0][1], DP[1][N-1]);
    for(int i=0;i<N-1;i++){
        int t = DP[0][i] + DP[1][i+2];
        int t2 = pointPrimary[i].second - pointPrimary[i+2].first;
        answer = max(answer, t2 > 0 ? t - t2 : t);
    }
    
    cout << answer << "\n";
    return 0;
}

 

PS. 이것이 정해인줄 알았는데, 다른 분들의 코드를 보니 메모리를 더 줄일 수 있는 방법이 있었다.