[BOJ 2109] 순회강연(c++)

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

---

문제 개요

n개의 대학에서 강연 요청이 들어오고, 각 대학은 d일 안에 강연을 하면 p만큼의 강연료를 지불합니다. 하루에 최대 한 곳에서만 강연할 수 있을 때, 최대로 벌 수 있는 돈을 구하는 문제입니다.

• (0 ≤ n ≤ 10,000)
• (1 ≤ d ≤ 10,000)
• (1 ≤ p ≤ 10,000)

---

문제 풀이

이 문제는 그리디 + 우선순위 큐로 해결하였습니다.

핵심 아이디어는 다음과 같습니다.

마감일 기준 내림차순 정렬: d가 큰 강연부터 처리하면, 마감일이 늦은 날짜부터 슬롯을 채워나갈 수 있습니다.

날짜별 슬롯 관리: 현재 처리 중인 마감일(idx)을 기준으로, 같은 d를 가진 강연들을 먼저 최대 힙(pq2)에 모아둡니다. 그 후 idx가 0보다 클 때까지 가장 강연료가 높은 것부터 하루씩 배정합니다.

탐욕적 선택: 마감일이 늦은 강연부터 처리하면서, 가능한 날짜 슬롯에 강연료가 높은 강연을 우선 배정하므로 최적해를 보장합니다. 예를 들어 예제에서 d=20인 강연(p=5)은 남은 슬롯이 많아 나중에라도 채울 수 있으므로, d=10인 강연(p=50)부터 처리해 나가는 방식입니다.

---

코드

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

int n, res;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	priority_queue<pair<int, int>> pq;
	priority_queue<int> pq2;
	cin >> n;
	int p, d;
	for (int i = 0; i < n; i++) {
		cin >> p >> d;
		pq.push({ d, p });
	}
	int idx = 10002;
	while (!pq.empty()) {
		idx = pq.top().first;
		while (!pq.empty()) {
			d = pq.top().first;
			p = pq.top().second;
			if (d != idx) break;
			pq2.push(p);
			pq.pop();
		}
		while (!pq2.empty() && d != idx) {
			res += pq2.top();
			pq2.pop();
			idx--;
		}		
	}
	while (!pq2.empty() && idx) {
		res += pq2.top();
		pq2.pop();
		idx--;
	}
	cout << res << '\n';
	return 0;
}