Backjoon_1202_그리디_보석도둑

1202-보석도둑

문제를 어떻게 풀어야 하는 지 감이 안잡혔다. 당직을 서면서 그냥 대충
가방무게 최소~ 가방무게 최대 사이에 있는 것들을 싸그리 넣고
비싼순으로 정렬시킨 다음 가방갯수만큼 더해주면 되는거 아닌가?? 라고 생각했지만,

만약 가방 최소무게보다 무조건 큰 보석밖에 없다면 답이 엉뚱하게 나온다.
3 2 | 3 65 5 23 3 99 | 10 1 => 99kg가 정답인데 164kg가 나온다.

Priority Queue 를 이용하자
그리디에서 어려운 문제는 자료구조랑 짬뽕이 되는 경우가 많은 것 같다.
데이터를 처리하는 과정에서 Queue,Deque,PQueue,Stack.. 등등 여러가지를 생각해보는게 좋을 것 같다.

일단 보석과 가방을 가벼운 순으로 정렬시킨다. 

각각의 가방에 대해 
	가방의 무게보다 보석의 무게가 작다면
    	pq.push()
        보석의 index 증가
    
    만약 pq가 비어있지 않다면 
    	pq의 top은 해당 가방무게에서 가져갈수 있는 가장 비싼 보석
        
        

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> jew;
vector<int> bag;
priority_queue<int> pq;
bool cmp(const pair<int, int>& a, const pair<int, int>& b) { return a.first < b.first; }
bool cmp2(int a, int b) { return a < b; }
int main()
{
	int N, K; cin >> N; cin.ignore(); cin >> K;
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a; cin.ignore(); cin >> b;
		jew.push_back({ a,b });
	}
	sort(jew.begin(), jew.end(), cmp);
	for (int i = 0; i < K; i++)
	{
		int b;
		cin >> b;
		bag.push_back(b);
	}
	sort(bag.begin(), bag.end(), cmp2);

	int j_idx = 0;

	for (int i = 0; i < K; i++)
	{
		
		while (j_idx < N && jew[j_idx].first <= bag[i])
		{
			pq.push(jew[j_idx].second);
			j_idx++;
		}

		if (!pq.empty())
		{
			ans += pq.top();
			pq.pop();
		}
	}
	cout << ans;

	return 0;
}