순회강연 2109

문제

접근 방법

처음에는 그저 뒤에서 접근하면 되는 줄 알았다.
하지만 뒤에서 접근하기 애매한 것이 있었는데 날짜순으로 할 시 더 큰 돈을 벌 수 있음에도 날짜가 촉박하기에 묻히는 것들이 있었다.
예를 들면 2일 1원, 2일 1원, 1일 3원이라 하면 2일이 더 높기에 1일 3원이 묻히는 것이다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    vector<vector<int>> v(10001, vector<int>());
    int n, ret = 0, topD = 0;
    cin >> n;
    while (n--)
    {
        int p, d;
        cin >> p >> d;
        v[d].push_back(p);
        topD = topD < d ? d : topD;
    }
    priority_queue<int> pq;
    for (int i = topD; i > 0; --i)
    {
        for (int d : v[i])
            pq.push(d);
        if (!pq.empty())
        {
            ret += pq.top();
            pq.pop();
        }
    }
    cout << ret;
    return 0;
}

풀이

끝나는 날짜를 줄여가며 우선순위 큐에 집어넣어 주면 해당 우선순위 큐에 가장 높은 값이 끝나는 날 전에 해낼 수 있는 가장 값비싼 일인 것이다.