[BOJ/백준][Gold4] 2109 : 순회강연 (C++)

[BOJ/백준][Gold4] 2109 : 순회강연 (C++)

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

2109번: 순회강연

 

[난이도] Gold4
[유형] Greedy

[풀이]
i일에는 d가 i 이상인 강연만 할 수 있다.
앞에서부터 생각하면 복잡하므로 뒤에서부터 가능한 강연료를 우선순위 큐에 추가하면 된다.
10000일이 최대이므로 i를 10000 ~ 1로 순회하면서 d가 i인 강연의 강연료 p를 우선순위 큐에 push하고
1개를 뽑으면 i일에 할 수 있는 최적의 강연을 뽑을 수 있다.

 

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int N,ans;
vector<int> a[10001];
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int p,d;
        scanf("%d%d",&p,&d);
        a[d].push_back(p);
    }
    priority_queue<int> pq;
    for(int i=10000;i>0;i--){
        for(auto k : a[i]) pq.push(k);
        if(!pq.empty()){
            ans+=pq.top();
            pq.pop();
        }
    }
    printf("%d",ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2109.cpp