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

이 문제는 그리디, multiset을 이용해서 풀었다.

 

이 문제에서 핵심 아이디어는 비싼 보석을 가장 작은 가방에 넣는 것이다.

 

보석의 경우 가격이 비싼 순으로, 같다면 가벼운 순으로 정렬을 해주고, 가방의 경우 multiset에 집어넣었다.

 

multiset을 처음 사용해봤는데, set과 다르게 중복을 허용하고 나머지는 같다.

또한 set, multiset 모두 기본적으로 오름차순 정렬이 되어있다고 한다.

 

보석을 순회하면서 multiset.lower_bound()를 통해 가장 적합한 가방을 찾고, 이를 빼주면 된다.

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

using namespace std;

int N, K;

bool compare(pair<int, int> &a, pair<int, int> &b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second > b.second;
}

typedef long long ll;

ll solve(vector<pair<int, int>> &jewelry, multiset<int> &package) {
	int maxSize = package.size();
	ll result = 0;

	for (pair<int, int> &jewel : jewelry) {
		int weight = jewel.first;
		int price = jewel.second;

		auto iter = package.lower_bound(weight);

		if (iter != package.end()) {
			result += price;
			package.erase(iter);
		}
	}
	
	return result;
}

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

	cin >> N >> K;

	vector<pair<int, int>> jewelry;
	for (int i = 0; i < N; i++) {
		int m, v;

		cin >> m >> v;

		jewelry.push_back({ m, v });
	}

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

	sort(jewelry.begin(), jewelry.end(), compare);

	ll answer = solve(jewelry, package);

	cout << answer << '\n';

	return 0;
}