[백준 1202번 / C++] 보석 도둑

<priority_queue> 자료구조

---

이 문제는 priority_queue 내림차순인 Max heap구조를 사용하면된다. 

먼저, 다음과 같은 예시가 주어졌다고 가정하자 

정렬되어있음.

테스트 케이스가 다음과 같이 주어졌을 때 오름차순으로 정렬을 한다. 

이후, 가방의 크기가 작은 것부터 해서 담을 수 있는 보석을 하나씩 다 담아본다. 

즉, 가방이 담을 수 있는 무게의 크기가 2라면 2이하인 보석들이 Queue에 빼곡빼곡 쌓여있다고 생각하면 된다. 그리고 더이상 담을 수 없는 무게의 보석이 등장하게 되면 Queue에 진열되어있는 보석들중 루트노드를 결과값에 더해주면 된다. Max_heap으로 구성되어있기 때문에 가장 가격이 비싼 보석이 루트노드에 있기 때문이다. 

 

두번째 가방에서도 Queue에다가 계속 집어넣으면서 배열의 끝을 만나거나 또는 담을 수 없는 보석의 무게가 등장하게 되면 큐의 루트노드를 pop() 하면서 결과값에 반영한다. 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std; 
int main() {	
	int n, k;
	cin >> n >> k; 
	vector<pair<int,int>> v1(n);
	vector<int> v2(k);
	for (int i = 0; i < n; i++) cin >> v1[i].first >> v1[i].second; 
	for (int i = 0; i < k; i++) cin >> v2[i]; 
	sort(v1.begin(), v1.end()); 
	sort(v2.begin(), v2.end()); 
	priority_queue <int> q;
	long long ans = 0; 
	int idx = 0; 
	for (int i = 0; i < k; i++) {
		while (idx < n && v1[idx].first <= v2[i])q.push(v1[idx++].second); 
		if (q.size()) {
			ans += q.top(); 
			q.pop(); 
		}
	}
	cout <<ans; 
}

 

1202번: 보석 도둑