Bin_S+StudyRoom

• 문제

한 저명한 학자에게 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값이 주어진다.

• 출력

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

• 예제 입력

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

• 예제 출력

185

• 접근방식

그리디 문제로 그리디는 Sort 아니면 PQ(Priority queue = 우선순위 큐)를 쓰거나 둘을 동시에 사용한다.

해당 문제는 오름 차순 정렬후, PQ에서 최소를 빼는 식으로 계산한다.

• 코드

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

using namespace std;

int n, p, d, result;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> p >> d;
        v.push_back({ d, p });
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++)
    {
        pq.push(v[i].second);
        if (pq.size() > v[i].first) // 오름 차순으로 정렬되어 있어서 1일차, 2일차 이런식으로 비교
        {
            pq.pop();
        }
    }

    while (pq.size())
    {
        result += pq.top();
        pq.pop();
    }

    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2109