1781_컵라면 (C++)

1781번: 컵라면

 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct Question{
	int deadline; int cup;
	
	bool operator< (Question question) const{ //오름차순
		if(deadline==question.deadline)
			return cup<question.cup;
		return deadline<question.deadline;
	}
};

int main(){
	int n;
	scanf("%d", &n);
	
	vector<Question> v;
	for(int i=0; i<n; i++){
		int a,b;
		scanf("%d %d", &a,&b);
		
		v.push_back({a,b});
	}
	
	sort(v.begin(), v.end()); //오름차순 정렬 (deadline기준)
	
	priority_queue<int> pq; //선택한 문제의 컵라면 저장
    
	for(int i=0; i<v.size(); i++){
		if(pq.size()<v[i].deadline) //데드라인이 아직 안됐으면
			pq.push((-1)*v[i].cup);
		else{
        	//데드라인이 지났지만, 기존에 선택한 문제보다 더 많은 컵라면을 얻을 수 있는 경우
			if(!pq.empty() && pq.top()*(-1)<v[i].cup){
				pq.pop();
				pq.push((-1)*v[i].cup);
			}
		}
	}
	
	int ans = 0;
	while(!pq.empty()){
		ans += (-1)*pq.top();
		pq.pop();
	}
	printf("%d", ans);
	
	return 0;
}

 

** 그리디 문제

" 현 위치에서 최적인 경우를 선택한다. "

즉, 계속해서 최적의 경우를 선택하며 갱신해나감!

 

 

 

---

 

 

데드라인을 기준으로, 더 많은 컵라면을 받을 수 있는 문제를 선택해야 한다.

=> 더 많은 컵라면을 받기 위해서는, ①데드라인 ②컵라면개수 를 따져야 함!!

 

 

① 데드라인

deadline을 기준으로 오름차순 정렬한다.

모든 문제를 선택할 지/선택하지 않을지 를 확인해야하므로, 컵라면의 개수(cup)도 함께 오름차순 정렬한다.

 

 

② 컵라면 개수

현재까지 선택한 컵라면을 저장하기 위해, 우선순위큐를 이용한다.

왜 우선순위큐를 이용했냐면 - 선택한 컵라면을 오름차순으로 저장하려고!

 

큐는 처음 size가 0이기 때문에, 현재의 시간으로 볼 수 있다. 따라서, 큐.size()와 deadline을 비교한다.

 

 1) 큐.size()가 deadline보다 작다면 == 아직 deadline이 되지 않았으므로, 해당 문제를 푼다. (해당 컵라면을 저장) : push

 

 2) 큐.size()가 deadline보다 크다면 == deadline이 지난 경우

     더 뒤의 deadline을 선택했을 때, 더 많은 컵라면을 받을 수 있는지를 확인한다.

     즉, '지금까지 선택된 컵라면 中 가장 적은 컵라면의 수' 는 큐.top()을 의미하므로(오름차순 정렬)

     선택된 문제 중 가장 적은 컵라면 수를 수정하여, 최적의 경우를 갱신해나간다. : pop&push