[백준 1202] 보석 도둑

보석 도둑 1202

유형

• 그리디
• 정렬

풀이

가방에 넣을 수 있는 보석 중에서 가격이 비싼 순서대로 가져가게 되면 총 가격의 최대값을 구할 수 있다. 보석의 가격 기준으로 내림차순하고 순회하면서 넣을 수 있는 가방이 있는지 확인하면 된다. 가방 크기를 벡터에 저장하고 사용하면 지우는 방식으로 하려고 하였지만 erase연산이 빠르지 않기 때문에 TLE가 날 수도 있었다. 그래서 multiset이라는 자료구조를 처음으로 사용해보았다.

multiset은 트리 기반의 자료구조로 set과 다른점은 중복된 키값을 가진다는 것이다. 그리고 lower_bound upper_bound 등 편리한 내장함수를 포함하기 때문에 이분 탐색시 유용하게 사용될 수 있을 것 같다.

보석들을 순회 하면서 가방 크기 중에서 lower_bound로 찾아서 들어가는 가방이 있으면 담고 그 가방은 erase하는 방식을 반복하면서 정답을 찾았다.

코드

#include <bits/stdc++.h>
using namespace std;

pair<int, int> v[300001];
multiset<int> bag;

bool cmp(pair<int, int>& a, pair<int, int>& b) { return a.second > b.second; }

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

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		bag.insert(a);
	}

	sort(v, v + n, cmp);

	long long ans = 0;
	for (int i = 0; i < n; i++) {
		auto iter = bag.lower_bound(v[i].first);
		if (iter != bag.end()) {
			ans += v[i].second;
			bag.erase(iter);
		}
	}

	cout << ans;


	return 0;
}