1202 보석 도둑(c++)

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

1202번: 보석 도둑

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int main()
{
	int n,k;
	cin>>n>>k;
	vector<pair<int,int>>v;
	vector<int>c;
	priority_queue<int>pq;
	for(int i=0;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		v.push_back(make_pair(a,b));
		
	}
	sort(v.begin(),v.end());
	for(int i=0;i<k;i++)
	{

			int w;
			cin>>w;
			c.push_back(w);
	}
	sort(c.begin(),c.end());
	int cnt=0;
	long long sum=0;
	for(int i=0;i<k;i++){
		while(cnt<n && c[i]>=v[cnt].first)
		{
			pq.push(v[cnt++].second);
		}
		if(!pq.empty())
		{
			sum+=pq.top();
			pq.pop();	
		}		
	}
	cout<<sum<<'\n';
	

}

<풀이 과정>

이 문제는 최대 힙 우선순위 큐(Maxheap)에 기반한 그리디 알고리즘이다. 각각의 가방의 무게와 가치를 pair벡터에 저장하고 각각의 가방의 무게를 벡터에 따로따로 저장한다. 그리고 가방이 가벼운 것부터 오름차순 정렬하고, 가방이 담을 수 있는 무게 또한 오름차순 정렬시킨다.

그 이후에, 가방의 무게를 초과하지 않으면서 가치가 큰 것부터 pq에 넣어줌으로써, 최대 가치를 얻을 수 있게 된다.