[백준] 1202번: 보석 도둑

📌 문제

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

📌 설명

처음에는 DP로 푸는 배낭 문제인 줄 알았지만 입력의 제한이 너무 컸다. 또한 가방이 여러 개이며 하나의 가방에 하나의 보석만 넣을 수 있다는 점이 배낭 문제와의 차이점이었다. 당연히 보석을 분할할 수 있다는 조건이 없으므로 그리디 알고리즘을 통한 배낭 문제로도 해결할 수 없다.

결론부터 말하자면 이 문제는 그리디하게 접근하는 문제이다. 기본적인 아이디어는 주어진 가방에 가격이 높은 보석부터 채우면 되는 것이다. 또한 들어갈 수 있는 가장 작은 가방에 들어가는 것이 좋다. 그래야지 보석을 더 많이 넣을 수 있을 것이다.

처음에는 가방의 무게를 vector로 저장하고 정렬 후 lower_bound()를 사용했다. 그러나 이 방법은 보석을 넣은 가방에 대한 후처리가 까다롭다는 것을 알았다. 가방의 무게를 저장할 적합한 자료구조를 찾아야 했다. 정렬이 되어야 하고 중복 원소를 허용해야 하며 중간에 존재하는 원소의 삭제가 용이해야 한다. 이를 만족하는 자료 구조는 multiset이다. multiset을 몇 번 사용하지 않아 떠올리기 쉽지 않았다. 또한 set, multiset이 lower_bound(), upper_bound()를 사용할 수 있다는 점도 처음 알았다.

또한 보석의 정보는 우선순위 큐로 저장해야 한다. 정렬 기준을 단순히 보석 가격으로 정렬하면 안 되는데, 보석의 가격이 같은 경우 무게가 작은 보석이 우선시 되어야 하기 때문이다. 우선순위 큐의 custom sort는 단순히 sort()의 cmp 함수 작성하듯이 하면 안 되고, 따로 구조체를 만들어야 한다. 이 점도 많이 사용하지 않았다 보니 까다로웠다.

어쨌든 위 사항들을 고려하여 작성하면 된다.

📌 코드

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

using namespace std;

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.first == b.first)
			return a.second > b.second;
		return a.first < b.first;
	}
};

int main() {
	int n, k;
	cin >> n >> k;

	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> gem;
	for (int i = 0;i < n;i++) {
		int m, v;
		cin >> m >> v;
		gem.push({ v,m }); // 가치, 무게
	}

	multiset<int> bag;
	for (int i = 0;i < k;i++) {
		int c;
		cin >> c;
		bag.insert(c);
	}

	// 가격이 높은 보석부터 가방에 넣는다.
	// 들어갈 수 있는 가장 작은 가방에 들어가는 것이 좋다.
	long long ans = 0;
	while (!gem.empty()) {
		int m = gem.top().second;
		int v = gem.top().first;
		gem.pop();

		auto iter = bag.lower_bound(m);

		if (iter != bag.end()) {
			ans += v;
			bag.erase(iter);
		}
	}

	cout << ans;
}