[1202번] 보석 도둑

* 문제

 

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

 

* 접근 방식

 

• 가벼운 가방부터 시작해서 현재 담을 수 있는 보석 중에 가장 비싼것을 고른다.
• 이를 위해 보석과 가방을 무게 오름차순 순으로 정렬하고, 우선순위 큐를 사용하여 가장 가치 있는 보석을 선택한다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;


int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n = 0;
	int k = 0;
	cin >> n >> k;

	vector<pair<int, int>> jewelries(n);
	vector<int> bags(k);
	// 무게, 가치
	for(int i = 0; i < n; ++i)
	{
		cin >> jewelries[i].first;
		cin >> jewelries[i].second;
	}

	for (int i = 0; i < k; ++i)
	{
		cin >> bags[i];
	}

	// 무게 오름 차순 정렬
	sort(jewelries.begin(), jewelries.end(), [](const pair<int, int>& a, const pair<int, int>& b) { return a.first < b.first; });
	sort(bags.begin(), bags.end(), [](int a, int b) {return a < b; });


	class Comparator
	{
	public:
		// 오름 차순 > 최대힙
		bool operator()(int a, int b) { return a < b; }
	};

	long long result = 0;
	priority_queue<int, vector<int>, Comparator> pq;
	int jewelryIndex = 0;
	for (int i = 0; i < k; ++i)
	{
		// 현재 무게를 만족하는 모든 보석들을 가치순으로 확인한다.
		int capacity = bags[i];

		while (jewelryIndex < n && capacity >= jewelries[jewelryIndex].first)
		{
			pq.push(jewelries[jewelryIndex++].second);
		}

		if (false == pq.empty())
		{
			result += pq.top();
			pq.pop();
		}
	}
	
	cout << result << endl;
	return 0;
}