[백준] 골드2 : (1202) 보석 도둑

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

 

가방은 오름차순으로 정렬한다.

가장 가벼운 가방으로 들 수 있는 보석들은 이후 모든 가방으로도 들 수 있기 때문이다.

 

보석은 무게를 기준으로 오름차순으로 정렬하되, 무게가 같은 경우, 가격순으로 내림차순으로 정렬한다.

훔칠 수 있는 보석 가격의 합의 최댓값을 구해야 하기 때문이다.

 

가방을 모두 순회하며 해당 가방의 무게로 들 수 있는 보석들을 우선순위 큐에 저장한다.

우선순위 큐는 무게와 상관없이 가격순으로 내림차순 정렬이 되도록 한다.

 

현재 가방 무게로 가장 비싼 보석을 더하고, 큐에서 제거한다.

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

bool Cmp(const pair<int, int>& a, const pair<int, int>& b)
{
	if (a.first == b.first) return a.second > b.second;
	return a.first < b.first;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	long long Answer = 0;
	cin >> N >> K;

	vector<pair<int, int>> Jewel(N);
	vector<int> Bag(K);

	for (int i = 0; i < N; ++i)
		cin >> Jewel[i].first >> Jewel[i].second;

	for (int i = 0; i < K; ++i)
		cin >> Bag[i];

	// 보석 무게 오름차순 정렬, 같은 무게면 가격순으로 내림차순 정렬
	sort(Jewel.begin(), Jewel.end(), Cmp);

	// 가방 무게 오름차순 정렬
	sort(Bag.begin(), Bag.end());
	
	// 현재 남은 가방 무게로 들 수 있는 보석들 / 가격순으로 내림차순 정렬
	priority_queue<int> SaveJewel;

	int Index = 0;
	for (int i = 0; i < K; ++i)
	{
		int Cur = Bag[i];

		// 현재 가방 무게로 들 수 있는 모든 보석을 저장
		// 가방 무게를 오름차순으로 정렬했기 때문에, 이전 가방으로 들 수 있는 보석은 이후 모든 가방에서도 들 수 있다.
		for (Index; Index < N; ++Index)
		{
			if (Jewel[Index].first <= Cur) SaveJewel.push(Jewel[Index].second);
			else break;
		}

		// 현재 가방 무게로 들 수 있는 보석들 중, 가장 비싼 보석 가져옴
		if (!SaveJewel.empty()) Answer += SaveJewel.top(), SaveJewel.pop();
	}

	cout << Answer << "\n";
}