[백준/BOJ] 백준 2109번 : 순회강연

https://www.acmicpc.net/problem/2109

2109번: 순회강연

 

마지막날부터, 첫째 날 순으로 해당 날짜에 강연할 수 있는 것 중 가장 강연료가 큰 강연을 고른다. 마지막날부터 고르는 이유는, 뒤에 날까지 강연해야 되는 강연들은 그 앞 날짜에도 강연할 수 있으므로, 마지막날부터, 첫째 날 순으로 해당 날짜에 강연할 수 있는 강연료들을 우선순위 큐에 강연료가 큰 게 먼저 나오도록 우선순위 큐에 넣으면서, 우선순위에서 가장 먼저 나오는 강연료를 선택하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n;
int result = 0;
vector<int> day_pay[10005]; //[날짜] = 해당 날짜 기간인것의 강연료

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

	cin >> n;

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

		day_pay[d].push_back(p);
	}

	priority_queue<int> pq;
	for (int i = 10000; i >= 1; i--) { //마지막 날 부터 선택한다 (뒤에 날 까지 기간인것은 앞에 날에서도 강연을 할 수 있으므로)

		for (int j = 0; j < day_pay[i].size(); j++) {
			pq.push(day_pay[i][j]);
		}

		if (!pq.empty()) {
			result += pq.top();
			pq.pop();
		}
	}

	cout << result;

	return 0;
}