문제

문제 링크

해설

해설에 앞서

• 이 링크에서 설명했듯, 그리디 문제는 sort() 후 priority_queue<>에 조건에 맞게 삽입해서 문제를 해결합니다.
• 그러므로 위 링크의 문제와 해결 코드가 상당히 비슷한 것을 확인할 수 있습니다.
  • 모든 문제는 푸는 데 1일이 소요되는 점 ↔ 모든 강연은 1일이 소요되는 점
  • 데드라인이 정해져 있는 점 ↔ 수익을 얻기 위한 기한이 정해져있는 점
  • 사실상 같은 문제라고 봐도 이상할 게 없습니다.
• 이번 문제로 다시 한 번 복습하도록 합시다.

문제풀이

• 최대 컵라면을 얻기 위해서는
  1. 데드라인에 최대한 아슬아슬하게 많은 문제를 풀어야 하고
  2. 같은 데드라인을 갖고 있는 문제 중에선 컵라면을 최대로 주는 문제를 풀어야 합니다.
• 이런 로직을 구현하기 위해서는 먼저 데드라인에 대해 오름차순 정렬(sort())한 뒤, min heap 우선순위 큐(priority_queue<>)에 삽입해야 합니다.
• n일에 최대한 풀 수 있는 문제의 개수는 n개 입니다.
  • 그러므로, 임의의 데드라인 d보다 우선순위 큐의 요소 개수가 크다면,
  • 우선순위 큐의 루트노드를 하나 제거합니다.
  • 그러면, 현재 기준 풀면 가장 손해인 문제(얻을 수 있는 컵라면 개수가 가장 적은 문제)가 삭제됩니다.
• 이런 이유 덕분에 정렬 후 우선순위 큐 삽입이 자동으로 그리디하게 요소를 선택하게 됨을 보장하는 것입니다.
• 참고로, 이 문제는 답의 범위가 2^(31)까지인 자연수이므로 안전하게 unsigned int 자료형을 사용했습니다.

코드

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
    int N;
	cin >> N;
	vector<pair<uint, uint>> q(N);	// deadline, cup
	for (int i = 0; i < N; ++i) cin >> q[i].first >> q[i].second;
	
	sort(begin(q), end(q));
	
	priority_queue<uint, vector<uint>, greater<>> pq;
	for (int i = 0; i < N; ++i) {
		pq.push(q[i].second);
		if (pq.size() > q[i].first) pq.pop();
	}
	int answer = 0;
	while (!pq.empty()) answer += pq.top(), pq.pop();
	cout << answer << '\n';
}

소스코드 링크

결과