[백준 c++] 2109 순회강연

문제 설명

https://www.acmicpc.net/problem/2109
한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력
첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

풀이

처음에는 기한 d을 기준으로 우선 오름차순 정렬하고 p를 차선으로 내림차순 정렬해서 풀었는데 그렇게 하면 다음과 같은 예시에서 11을 출력한다.

//반례
3
1 1
10 2
10 2

//answer:20

돈을 최대한으로 하는 것이 목표이기때문에 p를 우선 내림차순 정렬하여 풀어야한다. 스케줄 배열에 채워넣는 식으로 풀었다.
예를들어 기한이 10이라면 배열 idx 1~10까지 중에서 0인 칸 하나를 1로 바꾸는 것이다.

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, p, d, res, a[10001];
int main()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> q;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> p >> d;
        q.push({p, d});
    }
    while (!q.empty())
    {
        for (int i = q.top().second; i >= 1; i--)
        {
            if (!a[i])
            {
                a[i] = 1;
                res += q.top().first;
                break;
            }
        }
        q.pop();
    }
    cout << res << "\n";
}