[백준] 1202번: 보석 도둑 (c++)

 

문제

---

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

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

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

 

1202번: 보석 도둑

 

문제조건

---

• 1 ≤ N, K ≤ 300,000
• 0 ≤ Mi, Vi≤ 1,000,000
• 1 ≤ Ci≤ 100,000,000

 

풀이

---

한 번 확인한 보석은 다시 확인하지 않는 것이 중요한 문제였다. 이를 위해 보석과 가방을 모두 오름차순으로 정렬하였다. 각 가방에 대해 넣을 수 있는 보석을 모두 넣어본 후, 이들 중 가장 가격이 비싼 보석만 실제로 넣어주면 된다. 처음에 그냥 vector로 후보들을 넣은 후, sort해주어 가장 앞 값을 빼는 식으로 해 주었더니 시간 초과가 났다. 가방의 개수가 최대 100,000,000개이기 때문이다. 힙을 직접 구현 할 수 있겠지만 <queue>헤더의 priority_queue(우선 순위 큐)를 사용하여 풀어주었다.

 

코드

---

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

int n, k;
int bag[300001];
vector <pair <int, int>> jewel;
priority_queue<int> candidate;

bool cmp(int a, int b) {
	return b < a;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int m,v;
		cin >> m >> v;
		jewel.push_back({ m,v });
	}

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

	sort(jewel.begin(), jewel.end());
	sort(bag, bag + k);

	int idx = 0;
	long long ans = 0;
	for (int i = 0; i < k; i++) {
		while (idx < n && jewel[idx].first <= bag[i] ) {
			candidate.push(jewel[idx].second);
			idx++;
		}

		if (!candidate.empty()) {
			ans += candidate.top();
			candidate.pop();
		}
		
	}

	cout << ans;
}