백준 1202 - 보석 도둑

문제링크

• 백준 1202

문제설명

• 상덕이가 털 보석점에는 보석이 총 N개 있다.
• 각 보석은 무게 M 과 가격 V 를 가지고 있다.
• 상덕이는 K 개의 가방을 가지고 있고, 각 가방에 담을 수 있는 최대 무게가 각각 주어진다.
• 가방에는 최대 한 개의 보석만 넣을 수 있다.
• 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하라

문제접근

• 그리디 알고리즘 으로 푼다.
• 가방 -> 보석 을 선택할 수 있도록 한다.
• 현재 가방이 담을 수 있는 보석 중에서 가격이 가장 비싼 보석을 담아야 한다.
• 가방과 보석은 무게를 기준으로 오름차순 정렬을 한다.
• 보석을 담을 가방을 선택하고, 보석을 탐색하면서 담을 수 있는 보석의 경우 우선순위 큐에 담는다.
  • 우선순위 큐는 보석의 가격을 기준으로 최대힙 구조를 이룬다.
• 선택한 가방에 우선순위 큐의 top() 에 위치한 보석을 담는다.
• 위 과정을 모든 가방에 대해서 반복한다.

구현

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

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

	int N, K;
	cin >> N >> K;

	vector<pair<int, int>> gems;
	for (int i = 0; i < N; i++) {
		int mass, val;
		cin >> mass >> val;
		gems.push_back(make_pair(mass, val));
	}
	// 무게 순서로 오름차순 정렬
	sort(gems.begin(), gems.end());

	vector<int> bags;
	for (int i = 0; i < K; i++) {
		int mass;
		cin >> mass;
		bags.push_back(mass);
	}
	// 무게 순서로 오름차순 정렬
	sort(bags.begin(), bags.end());
	
	int idx = 0;
	long long ans = 0;
	priority_queue<int> pq;
	for (int i = 0; i < K; i++) {
		int cBag = bags[i];
		while (cBag >= gems[idx].first && idx < N) {
			pq.push(gems[idx++].second);
			if (idx == N) break;
		}
		if (!pq.empty()) {
			ans += pq.top();
			pq.pop();
		}
	}
	cout << ans << "\n";
}