[BOJ] 1781번 컵라면 (C++)

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

1781번: 컵라면

 

#include <iostream>
#include <queue>
using namespace std;

struct cmp{
	bool operator()(pair<int, int>&a, pair<int, int>&b){
		if(a.first == b.first){
			return a.second < b.second;
		} else{
			return a.first > b.first;
		}
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	priority_queue<int, vector<int>, greater<int>> pqAns;
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		pq.push({a, b});
	}
	
	long long answer = 0;
    int time = 1;
	while(!pq.empty()){
		pair<int, int> cur = pq.top();
		pq.pop();
		if(cur.first >= time){
			pqAns.push(cur.second);
			time++;
		} else if(pqAns.top() < cur.second){
			pqAns.pop();
			pqAns.push(cur.second);
		}
	}
	while(!pqAns.empty()){
		answer += pqAns.top();
		pqAns.pop();
	}
	cout << answer << endl;
	return 0;
}

 

이 문제의 핵심은 선택하지 않는 것이 더 최적인 경우를 고려하는 것이다.

 

1. 데드라인은 오름차순, 데드라인이 같다면 컵라면 개수를 내림차순으로 문제 정렬

2. 문제를 차례대로 탐색

3-1. 현재 문제의 데드라인이 경과 시간보다 크다면 문제를 풀 수 있는 경우 -> 현재 문제를 푼 것으로 취급

3-2. 현재 문제의 데드라인이 경과 시간보다 작다면 문제를 풀 수 없는 경우 -> 가장 적은 컵라면을 주는 문제 대신 현재 문제를 푸는 것이 이득이라면 현재 문제를 푼 것으로 취급