백준 2109번 순회강연 - C++ 풀이

---

 

1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다.

 

1. 시간 역순으로 매일 가장 강연료를 많이 받을 수 있는 강연을 고른다.

 1781번 컵라면 문제와 동일한 문제이다. 13904번 과제 문제와도 동일하다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (강연료 = 컵라면이라고 생각하면 된다.)

백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명

반응형

---

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

using namespace std;

int N;
vector<int> lectures[10001];

int optimize() {
    int ret = 0;
    priority_queue<int> pq;
    
    for (int day=10000; day>0; day--) {
        for (auto lecture: lectures[day]) pq.push(lecture);
        if (!pq.empty()) {
            ret += pq.top();
            pq.pop();
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        int p, d;
        cin >> p >> d;
        
        lectures[d].push_back(p);
    }
    
    cout << optimize();
    
    return 0;
}