1781 - 컵라면

문제

코드

#include <bits/stdc++.h>
using namespace std;

int n,p,c,ret;
vector<pair<int,int>> v;

int main(){
	cin >> n;
	
	for(int i = 0; i <n; i++){
		cin >> p >> c;
		v.push_back({p,c});
	}
	
	sort(v.begin(), v.end());
	
	priority_queue<int, vector<int>, greater<int>>pq;
	
	for(int i = 0; i < n; i++){
		pq.push(v[i].second);
		if(pq.size() > v[i].first){
			pq.pop();
		}
	}
	while(pq.size()){
		ret += pq.top();
		pq.pop();
	}
	cout << ret << '\n';
}

풀이

문제마다 데드라인이 있기 때문에 뒤죽박죽 놓는 것보다 문제의 데드라인 순으로 정렬을 하는 것이 편하다.
데드라인을 기준으로 정렬되어 있고 우선 순위 큐에 1일차 문제를 모두 담는다.
문제는 하루에 하나가 최대이기 때문에 pq 사이즈가 넘을 때 오름차순으로 정렬된 pq의 top을 사이즈에 맞게 pop한다. 그러면 결국 1일차에는 1일차에 얻을 수 있는 컵라면의 갯수가 최대인 문제가 담긴다. 날짜를 진행시키며 pq의 size에 맞게 같은 방식을 진행한다면 2일차에 컵라면을 많이 주는 문제가 2개라면 그 두 문제가 남게 된다.
최댓값을 구하기 위해 최소 값들을 삭제시켜 나가는 방식이다.

결과

후기

이전에 같은 유형을 풀어 본적이 있어서 금방 풀 수 있는 문제였다.