1202 보석 도둑

greedy 방식으로 접근하려 했으나, 부분 최적해를 구하는 방식이 특이한 문제이다.

내가 시도했던 접근은 bottom-up 방식이 greedy 였으며, 메모리 제한때문에 테이블 구성에 제약이 생기는 것과 local optimal을 구하는 과정이 매끄럽지 못했다.

 

그래서 찾아본 방법으로 js1jj2sk3.tistory.com/14를 참고했는데, 방법은 다음과 같다.

• Greedy 방식의 정당성 증명 : 무게 제한 순으로 A1, A2, ...의 가방들은 A1이 담을 수 있는 보석은 A2도 담을 수 있으므로, 배낭의 수용량이 높을수록 더 비싼 보석을 넣는게 최적해이다.
• 구현 방법은 우선순위 큐가 핵심인데, 배낭의 무게와 보석의 가치를 정렬하고 i번째 배낭이 담을 수 있는 보석들의 가치 중에서 최대 가치를 뽑아내도록 한다.

고찰

Greedy 알고리즘은 local optimal을 어떻게 구성하는지가 핵심이기 때문에 정렬과도 연관되어 문제가 나오는걸로 보인다.

정답코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX_SIZE 300000
pair<int, int> jew[MAX_SIZE];
int bp[MAX_SIZE] = { 0, };
int N, K;
int main()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> jew[i].first >> jew[i].second;
	}
	for (int i = 0; i < K; i++) {
		cin >> bp[i];
	}
	
	//무게 제한이 낮은 가방이 가장 비싼 보석을 넣도록 정렬
	sort(jew, jew + N);
	sort(bp, bp + K);

	long long result = 0;
	int idx = 0;
	priority_queue<int> pq;

	for (int i = 0; i < K; i++) {
		//i번째 배낭의 무게 제한에 걸리지 않는 보석들은 다 넣어본다.
		while (idx < N && jew[idx].first <= bp[i])
			pq.push(jew[idx++].second);

		//넣은 값들 중에서 최대 값을 뽑아낸다.
		if (!pq.empty()) {
			result += pq.top();
			pq.pop();
		}
	}
	cout << result;
	return 0;
}