1781 - 컵라면

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

1781번: 컵라면

생각해 보기

1. 정방향(시간의 흐름) 대로 진행을 한다면 데드라인을 전부 체크하고 그 다음 데드라인에는 이전 데드라인을 전부 빼줘야하는 번거로운 과정이 진행된다.
2. 역순으로 생각해 보자. 데드라인을 최대값으로 잡아놓고 역으로 줄여 나간다면?
3. 데드라인이 증가가 아닌 감소이므로 범위만 늘려나가면 된다. 그러면 이전 데드라인에 걸리는 친구들을 제거하는 과정이 사라진다.
4. 헌데 그 범위 내에서 최적(컵라면이 제일 많이 받는 문제)를 알려면 지속해서 max_element와 같이 최대 값을 찾는 알고리즘을 사용해야 한다.
5. prority_queue를 사용해서 top에서 하나씩 빼오자.
6. 만약 pq가 비었다면 데드라인만 감소시키면 된다.
7. 더 최적화를 하고 싶다면 없는경우 idx위치의 데드라인 값을 T에 주고 진행시키면 불필요한 T감소가 줄어들게 된다.

예제

3
1 1
2 50
2 100

답 : 150

코드

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

using namespace std;

int N, T=0;
vector<pair<int, int> > cups;

struct sort_queue{
    bool operator()(pair<int, int> &a, pair<int, int> &b){
        return a.second < b.second;
    }
    
};

bool sort_vector(pair<int, int> &a, pair<int, int> &b){
    return a.first > b.first;
}

void input(){
    cin>>N;

    int a,b;
    for(int i=0;i<N;++i){
        cin>>a>>b;
        cups.push_back({a,b});
        T=max(T,a);
    }
}

void solution(){
    priority_queue<pair<int, int>, vector<pair<int, int> >, sort_queue> pq;
    sort(cups.begin(), cups.end(), sort_vector);

    int ans = 0, idx = 0;
    for(;T > 0; --T){
        while(idx < N && cups[idx].first >= T){
            pq.push({cups[idx].first, cups[idx].second});
            ++idx;
        }
        
        if(!pq.empty()){
            ans+=pq.top().second;
            pq.pop();
        }
    }

    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}