[백준] 1781번 컵라면 (C++)

 

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

 

 

문제 설명

데드라인과 컵라면의 수가 주어졌을 때, 데드라인 내에 문제를 풀면 해당 컵라면을 받을 수 있다

받을 수 있는 최대 컵라면의 수를 구하는 문제이다.

 

주요 로직

1. 그리디 문제이기에 우선순위 큐를 통해 풀어야 한다.

-> 오름차순의 우선순위 큐를 선언하여 하나씩 넣고 데드라인을 넘어서면 pop()한다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n, d, c;
vector<pair<int,int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> d >> c;
		v.push_back({d,c});
	}
	
	sort(v.begin(), v.end());
	
	for(int i=0; i<n; i++){
		pq.push(v[i].second);
		if(pq.size() > v[i].first) pq.pop();
	}
	
	int cnt = 0;
	while(pq.size()){
		cnt += pq.top();
		pq.pop();
	}
	
	cout << cnt << "\n";
	return 0;
}