[백준 1202] 보석 도둑 (C++)

이 문제는 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 구하는 문제이다.

최댓값을 구하려면, 보석의 가치가 가장 높은 것들만 골라 훔치면 된다.

하지만, 가방마다 담을 수 있는 무게의 최댓값이 결정되어 있어서 가치가 높더라도 담지 못하는 겅우가 발생할 수 있다.

즉, 우리는 가치가 높은 보석부터 차례로 담을 수 있는 가방이 존재하는지 확인한 뒤 담을 수 있는 가방이 존재하면, 그 가방에 담을 수 있는 최대 무게 $C_i$가 최소인 가방을 선택해 담고 해당 가방을 제외한 다른 가방에 다른 보석들을 담아나가면 된다.

따라서, 우리는 보석을 가치순으로 정렬한 뒤, 해당 보석을 담을 수 있는 가방 중 $C_i$가 최소인 것을 제거하면 되는 상황이다.

단순히 구현하면, O(NK)로 보석에 대응되는 가방을 찾는 과정으로 인해 시간 초과가 발생함을 알 수 있다.

따라서, 이분탐색으로 대응되는 가방을 찾는 과정은 O(logK)로 줄일 수 있지만, 해당 가방을 사용했다는 의미로 삭제시에 O(K)의 시간복잡도가 되므로 결국에 보석 N개에 대해 O(K)번의 연산이 되므로 시간복잡도는 여전히 O(NK)가 된다.

따라서, 삭제에서도 시간 복잡도를 낮춰야한다. 즉, 연결 리스트나 트리 형태의 자료 구조를 사용해야한다.

하지만, 연결 리스트는 random-access가 불가능해 이분 탐색을 할 수 없는 것이 일반적이다.
C++ STL에서는 iterator를 통해 이것이 가능하도록 하지만, 이는 결국 mid를 찾는 과정이 O(N)의 시간복잡도를 가짐을 시사한다.

따라서, 트리 형태의 자료구조로 보석을 담을 가방을 찾아, 전체 시간 복잡도를 O(NlogK)로 낮춰줄 수 있다.

이것을 최소힙을 이용해 담을 수 있는 가방이 나올 때 까지 pop해나가도 되지만, 이진 탐색 트리를 통해 손쉽게 해당 가방을 구할 수 있으므로 C++의 multiset을 이용해 구현하면 된다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, k;
pair<int, int> jewels[300'000]; // {V, M}
multiset<int> bags;

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

	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> jewels[i].Y >> jewels[i].X;
	sort(jewels, jewels + n);

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

	long long ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		int m, v;
		tie(v, m) = jewels[i];
		auto it = bags.lower_bound(m);
		if (it == bags.end()) continue;
		ans += v;
		bags.erase(it);
	}
	cout << ans;
}