백준 1781 컵라면 C++

해설

문제를 처음 보자마자 그리디 알고리즘인 것을 깨닫고 우선순위 큐를 사용하였다.

 

n과 데드라인이 20만까지 나올 수 있으므로, n이 20만이고, 모든 숙제의 데드라인이 20만인 경우의 수를 생각해봐야 한다.

 

데드라인에 맞춰 가장 큰 컵라면의 수를 뽑을려 하면 시간초과에 걸린다.

 

그렇기에 반대로 생각해서 날짜를 정한다.

제일 처음 날짜부터 차례대로 정해두고 가장 큰 컵라면의 수를 꺼내면 문제를 풀 수 있다. 이때, 데드라인때문에 삭제될 수 있는 값들은 우선순위 큐를 하나 더 이용해서 지우는 것이 포인트이다.

 

답

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    priority_queue<pair<ll,ll>> q;
    ll ans=0,a,b;
    for(int i=0;i<n;++i){
        cin>>a>>b;//day,gae
        q.push({-a,b});
    }
    vector<ll> v(200001,0);
    int crnDay=1;
    priority_queue<pair<ll,ll>> ansQ; //gae, idx
    while(!q.empty()){
        ll day=-q.top().first;
        ll gae=q.top().second;
        q.pop();
        if(crnDay<=day){
            v[crnDay]=gae;
            ansQ.push({-gae,crnDay});
            crnDay++;
        }
        else{
            int tmpGae=-ansQ.top().first;
            int tmpDay=ansQ.top().second;
            if(gae<tmpGae) continue;
            else{
                v[tmpDay]=gae;
                ansQ.pop();
                ansQ.push({-gae,tmpDay});
            }
        }
    }
    for(int i=1;i<=200000;++i){
        ans+=v[i];
    }
    cout<<ans;
}