백준 13904번. 과제(c++) / Greedy

오랜만에 그리디 문제를 풀어봤다.

역시 그리디는 아이디어를 도출해내는 것이 참 어렵다...ㅎ

하지만, 그렇게 어려운 그리디 문제에 속하지는 않아서 생각보다 간단하게 해결할 수 있었다.

 

우선순위큐를 사용했고

맨 마지막에 있는 마감일 기준으로 우선순위큐에 값을 넣어서 각 날마다 가장 큰 값을 더해주었다.

아래는 놓치기 쉬운 반례들이다.

 

6
5 3
5 3
5 3
4 2
4 1
4 2
정답 : 13

 

4
9 9
9 9
9 9
1 10
정답 : 37

 

// 과제
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int n, d, w;
int ans = 0;
vector<pair<int, int>> work;
priority_queue<int> pq;
 
bool cmp(const pair<int, int> &a, const pair<int, int> &b){
    if(a.first==b.first){
        return a.second>b.second;
    }
 
    return a.first>b.first;
}
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>d>>w;
        work.push_back(make_pair(d, w));
    }
 
    sort(work.begin(), work.end(), cmp);
 
    int days = work[0].first;
    int idx = 0;
    while(idx<n){
        while(days==work[idx].first){
            int deadline = work[idx].first;
            int score = work[idx].second;
            pq.push(score);
            idx++;
        }
        days--;
        if(pq.empty()) continue;
        ans += pq.top();
        pq.pop();
    }
    
    while(days-- && !pq.empty()){
        ans += pq.top();
        pq.pop();        
    }
 
    cout<<ans<<"\n";
    return 0;
}