[백준] 골드2 : (1781) 컵라면

문제: https://www.acmicpc.net/problem/1781

 

최대 데드라인을 초과하지 않는 범위에서 가장 많은 컵라면을 얻는 문제이다.

 

ex)

7
1 9
1 100
2 300
2 99
3 100
5 100
5 999

 

다음 예시에서, Day1에서는 1~5 데드라인의 문제를 모두 풀 수 있다.

그리고, Day5에서는 5 데드라인의 문제만이 풀 수 있다.

 

따라서, 이 문제는 마지막 날부터 역순으로 계산하는 것이 핵심인 문제이다.

 

데드라인을 하나씩 줄여가며, 각 날짜에 풀 수 있는 문제들을 우선순위 큐에 넣는다.

(우선순위 큐는 그러면 계속 풀 수 있는 문제 후보군들이 남아있다)

각 날마다 우선순위 큐 안에서 보상이 가장 큰 문제를 선택하여 정답에 더하고, 큐에서 뺀다.

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

ll N, DeadLine, Answer;
priority_queue<ll> pq;

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

	cin >> N;

	vector<pair<ll, ll>> Problem(N); // { 데드라인, 컵라면 수 }

	for (ll i = 0; i < N; ++i)
	{
		cin >> Problem[i].first >> Problem[i].second;
		DeadLine = max(DeadLine, Problem[i].first);
	}

	// 문제들을 데드라인 순으로 오름차순, 보상 순으로 내림차순 정렬
	sort(Problem.begin(), Problem.end());

	int CurrentDay = DeadLine;	// 마지막 날짜부터 시작
	int Index = N - 1;			// 마지막 문제부터 처리

	// 마지막 날부터 첫날까지 순차적으로 처리
	while (CurrentDay > 0)
	{
		// 현재 날에 처리 가능한 문제들을 큐에 넣기
		while (Index >= 0 && Problem[Index].first >= CurrentDay)
		{
			pq.push(Problem[Index].second);
			Index--;
		}

		// 큐에서 보상이 가장 큰 문제를 꺼내서 처리
		if (!pq.empty())
		{
			Answer += pq.top();
			pq.pop();
		}
		CurrentDay--;
	}
	cout << Answer << "\n";
}