취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1781번 문제인 컵라면이다.
문제는 아래 링크를 확인하자.

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

어떤 한 문제가 있을 때, 이 문제를 일찍 풀 수도 늦게 풀 수도 있다면 이 문제는 가능한 늦게 푸는 것이 좋다는 점을 관찰하자. 문제를 풀었을 때 컵라면을 주는 기간은 모두 동일한 날부터 시작하므로, 문제를 늦게 풀면 풀 수록 다른 문제의 데드라인 내 풀 수 있는 문제의 수를 가장 적게 간섭하게 되기 때문이다.

따라서 마지막 날서부터 문제들을 살펴보면서, 그 날 풀 수 있으면서 가장 많은 컵라면을 얻을 수 있는 문제를 순서대로 찾아나가는 것으로 문제를 해결할 수 있다.

이 구현은 우선순위 큐(priority queue)를 이용하여 간단히 해낼 수 있다.

아래는 제출한 소스코드이다.

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

priority_queue<pair<int, ll>> pq1;
priority_queue<ll> pq2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		pq1.push(make_pair(x, y));
	}

	ll ans = 0;
	for (int i = N; i > 0; i--) {
		while (!pq1.empty()) {
			if (pq1.top().first == i) {
				pq2.push(pq1.top().second);
				pq1.pop();
			}
			else break;
		}
		if (!pq2.empty()) {
			ans += pq2.top();
			pq2.pop();
		}
	}

	cout << ans;
}