BOJ_1781_컵라면(2109_순회공연)

컵라면

순회공연

두 문제는 거의 완전히 동일하니 같이 작성하겠다.

문제가 얘기하고자 하는 것은
각 데드라인에 대해 얻을 수 있는 최댓값을 결정짓는 문제이다.

그와 관련된 모든 문제는 Priority Queue를 사용해야 한다.
그리고, Priority Queue 안에는 문제에 조건에 대응하는 경우만 들어가 있어야 한다.

데드라인이 빠른 순으로 정렬한다. (같다면 점수가 큰 순으로)
해당 데드라인에 대해 최선의 것들만을 우선순위 큐에 남겨놓는다.

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

int main()
{
	int N; cin >> N;
	vector<pair<int, int>> v;
	priority_queue<int> pq;
	int deadline;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b }); // 순회공연의 경우 v.push_back({b,a});
	}

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

	for (int i = 0; i < N; i++)
	{
		deadline = v[i].first;
		pq.push(-v[i].second);

		// 해당 데드라인까지 최선의 것들만을 남겨놓는다. 
		while (deadline < pq.size())
		{
			pq.pop();
		} 
	}
	int ans = 0;
	while (!pq.empty())
	{
		ans += pq.top();
		pq.pop();
	}
	cout << -ans;
	return 0;
}