백준 2109 순회강연 풀이(c++)

문제 링크

성능 요약

메모리: 2292 KB, 시간: 4 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬

제출 일자

2025년 3월 5일 13:12:04

문제 설명

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

출력

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

 

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

using namespace std;

int N, iResult = 0;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    vector<pair<int, int>> v;
    int iCost, iDay;

    for (int i = 0; i < N; ++i)
    {
        cin >> iCost>> iDay;
        v.push_back({ iDay, iCost });
    }

    sort(v.begin(), v.end());
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < N; ++i)
    {
        pq.push(v[i].second);
        if (pq.size() > v[i].first)
            pq.pop();
    }

    while (!pq.empty())
    {
        iResult += pq.top();
        pq.pop();
    }
    cout << iResult;
    return 0;
}

 

priority queue와 정렬을 통하여 풀이.

어떠한 기준으로 정렬을 해야할지 생각하는 부분이 어려웠다.