[priority queue] [multiset] 보석 도둑 1202

문제 해설 및 주의사항

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

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

 

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

풀이

- 브루트 포스?

: N 과 K 의 최댓값. 300,00 만 보아도 브루트 포스가 절대 되지 않을 것이라고 짐작할 수 있다.

 

- 그리디 알고리즘 (a 와 b 는 결국 같은 알고리즘이다.)

a. 가방에 가장 비싼 것을 담는다. (담을 수 있는 무게 순으로 가방을 오름차순으로 정렬하여, 무게를 초과하지 않고, 가장 비싼 보석을 담는다.)

풀이코드 (a)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;
// 1202 보석 도둑
struct jewel{
	int weight, value, isBag;
};

// 무게의 오름차순. 무게가 같으면 가방이 앞으로
bool cmp(jewel& u, jewel& v){
	return u.weight < v.weight || (u.weight == v.weight && u.isBag < v.isBag);
}

int main(){
	int n, k;
	
	scanf("%d %d", &n, &k);
	vector<jewel> jewels(n + k);
	
	for(int i = 0 ; i < n; i++){
		scanf("%d %d", &jewels[i].weight, &jewels[i].value);
	}
	
	for(int i = 0; i < k; i++){
		scanf("%d", &jewels[i + n].weight);
		jewels[i + n].isBag = 1;
	}
	
	// 가방과 보석은 무게순, 오름차순으로 정렬
	sort(jewels.begin(), jewels.end(), cmp);
	
	priority_queue<int> q;
	
	long long ans = 0;
	for(auto &obj : jewels){
		// 현재 보석이라면, 값을 우선순위 큐에 삽입한다.
		if(obj.isBag == 0){
			q.push(obj.value);
		}
		else{
		// 현재 가방이라면, 
			if(!q.empty()){
				// 우선순위 큐가 비지 않았다면, 우선순위 큐의 최댓값을 더하고, pop 한다.
				ans += (long long)q.top();
				q.pop();
			}
		}
	}
	printf("%lld\n",ans);
}

b. 가격이 높은 보석부터 차례대로, 보석을 담을 수 있는 가방 중 C[i] 가 가장 작은 가방에 넣는다.

b-1. 보석의 값보다 큰 숫자 중에 가장 작은 수를 찾는다. (lower bound)

b-2. 수를 지운다.

Binary Search Tree (multiset) 를 사용하면, 두 연산을 O(log K) 에 가능하다.

 

풀이코드 (b)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;
// 1202 보석 도둑
struct jewel{
	int weight, value;
};

// 보석 값의 내림차순
bool cmp(jewel& u, jewel& v){
	return u.value > v.value;
}

int main(){
	int n, k;
	
	scanf("%d %d", &n, &k);
	vector<jewel> jewels(n);
	
	for(int i = 0 ; i < n; i++){
		scanf("%d %d", &jewels[i].weight, &jewels[i].value);
	}
	
	sort(jewels.begin(), jewels.end(), cmp);
	
	multiset<int> s;
	
	for(int i = 0; i < k; i++){
		int t;
		scanf("%d", &t);
		// 가방의 최대 무게들을 넣어줌
		s.insert(t);
	}
	
	long long ans = 0;
	for(int i = 0 ; i < n; i++){
		// i 번째 보석의 하한 (가방 최대 무게)
		auto it = s.lower_bound(jewels[i].weight);
		
		// 하한이 존재한다면
		if(it != s.end()){
			// 현재 보석 값을 더하고
			ans += jewels[i].value;
			// 쓴 가방은 없앤다.
			s.erase(it);
		}
	}
	printf("%lld\n", ans);
}

 

---

퇴고