백준 1202번: 보석 도둑

[문제 링크]

1202번: 보석 도둑

---

재밌는 그리디 알고리즘 문제였다.

 

입력받는 보석의 무게와 가격은 pair 컨테이너에 담고 가격을 기준으로 내림차순 정렬을 해주었고,

가방에 담을 수 있는 무게는 로그시간에 검색을 할 수 있도록 연관 컨테이너인 multiset 컨테이너에 오름차순으로 담아주었다.

 

가장 비싼 보석부터 해당 보석의 무게를 담을 수 있는 가방 중에서 가장 작은 무게의 가방을 선택하고, 담을 수 잇는 가방이 없다면 넘어가는 방식으로 구현하였다.

---

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

long long Greedy(vector<pair<int, int>>& jew, multiset<int>& bag, int N, int K)
{
	sort(jew.begin(), jew.end(), greater<pair<int, int>>()); // 보석 가격을 기준으로 오름차순 정렬

	int here = 0;
	long long sum = 0;

	while (!bag.empty() && here < N)
	{
		multiset<int>::iterator lowIter = bag.lower_bound(jew[here].second);
		if (lowIter != bag.end()) // 선택한 무게의 보석을 넣을 수 있는 가방이 존재한다면
		{
			sum += jew[here].first;
			bag.erase(lowIter);
		}

		here++;
	}

	return sum;
}

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

	int N, K;
	cin >> N >> K;

	vector<pair<int, int>> jew(N);
	for (int i = 0; i < N; i++)
		cin >> jew[i].second >> jew[i].first;

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

	cout << Greedy(jew, bag, N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 123 day