백준 1202: 보석 도둑

문제 요약

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

문제 풀이

어쨌든 가치가 가장 높은 보석을 가능한 한 담으면 되는 그리디 알고리즘이다. 이 풀이의 핵심은 우선순위 큐에 있는데, 각 보석을 pair<int, int>로 정의하고, 비교문을 직접 작성하여 우선순위 큐로 넣어주었다.

가치가 높을수록 우선순위를 높게 설정하여 해당 보석을 우선적으로 수집할 수 있도록 한다. 그리고 우선순위 큐를 top부터 돌리면서 알맞은 가방을 탐색하면 되는데, 이때 O(logn)의 퍼포먼스를 보여주는 multiset을 이용하였다.

가방의 무게를 multiset에 삽입하여 정렬하였고, 결국 어떠한 보석을 수집할 때에 그 보석의 무게보다 같거나 큰 가방 중 가장 작은 값, lower_bound()를 써서, 그 가방이 존재하는지 탐색하였다. 없다면 그 보석은 수집할 수 없고, 있다면 그 가방을 multiset에서 삭제하고 보석의 가치를 누적시켜주었다.

결국 우선순위가 가장 높은(보석의 가치가 가장 높은) 순서대로 보석을 수집하는 것이 중요하며, 해당 보석을 담을 수 있는 가방의 탐색이 다음 과제이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

struct Pred {
	bool operator() (pair<int, int> p1, pair<int, int> p2) {
		return p1.second < p2.second;
	}
};

int main()
{
	int n, k, in, in2;
	long long res = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, Pred> q;
	multiset<int> s;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &in, &in2);
		q.push({ in,in2 });
	}
	for (int i = 0; i < k; i++) {
		scanf("%d", &in);
		s.insert(in);
	}
	while (!q.empty() && !s.empty()) {
		auto& temp = q.top();
		auto iter = s.lower_bound(temp.first);
		if (iter != s.end()) {
			res += temp.second;
			s.erase(iter);
		}
		q.pop();
	}
	cout << res;

	return 0;
}

후일담

푸는데 생각보다 오래걸렸는데, 가방을 multiset으로 설정한다는 발상을 빠르게 떠올렸다면 조금 더 일찍 풀 수 있었을 것 같다.