C++ 백준 1202번

백준 1202번 www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

 

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

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

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

 

가방이 두 개가 있고 C1 = 2, C2 = 10 (가방에 담을 수 있는 최대 무게) 일 때

보석이

M1 = 1 V1 = 65, (보석 1)

M2 = 5 V2 = 23, (보석 2)

M3 = 2 V3 = 99 (보석 3)이면  

1번 가방은 무게가 2인 것 까지 들어갈 수 있으니까 무게가 1인 보석 1과 무게가 2인 보석 3이 들어갈 수 있는데 이 두 개 중 보석 3번의 가격이 99로 더 높으니까 3번 보석을 넣는다. 그다음 2번 가방은 무게가 10인 것 까지 들어갈 수 있는데 1번 가방에 못 넣은 1번 보석과 무게가 5인 2번 보석이 들어갈 수 있다. 이 중에서 가격이 더 큰 건 보석 1이니까 총가방에 들어갈 수 있는 최대 가격은 164이다.

 

가방이 무게 순으로 오름차순으로 정렬돼있고 보석도 무게 순으로 오름차순으로 정렬돼있다고 가정하고 일반화를 시켜보면 

1번 가방에는 1번 가방과 무게가 같거나 작은 보석 순서까지 들어갈 수 있는데 그중에서 가격이 가장 큰 애를 넣으면 되고

그다음 가방에는 그 전 가방에 들어간 친구 뺀 남은 보석과 거기에 이 가방과 무게가 같거나 작은 보석 순서까지 더 들어갈 수 있는데 거기서 가격이 가장 큰 애를 넣으면 된다.

항상 맨 위에 가격이 가장 큰 애가 있을 수 있게 우선순위 큐를 사용하면 된다.

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

int main() {
	int n, k;
	long long answer = 0;
	cin >> n >> k;
	vector<pair<int,int>> a(n); // 보석 
	vector<int> b(k); // 가방 최대무게 저장
	priority_queue<int> pq;
	for (int i = 0; i < n; i++) { // 보석의 무게 m, 가격 v 저장
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end()); // 보석 무게를 기준으로 오름차순 정렬
	for (int i = 0; i < k; i++) {
		cin >> b[i];
	}
	sort(b.begin(), b.end()); // 가방도 무게를 기준으로 오름차순 정렬
	int index = 0;
	for (int i = 0; i < k; i++) {
		while (index < n && a[index].first <= b[i]) {
			pq.push(a[index++].second);
		} // i번째 가방이 담을 수 있는 모든 보석을 최대힙에 넣음
		if (!pq.empty()) {
			answer += (long long)pq.top();
			pq.pop();
		}
	}
	cout << answer << '\n';
}

+)jaimemin.tistory.com/760 우선순위 큐를 이용해서 최대힙에 넣는 부분은 이 블로그를 참고했습니당