[백준 1202번 C/C++] 보석 도둑

 

[백준 1202번 C/C++] 보석 도둑

 

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

---

 

해결전략

 

그리디 알고리즘 Greedy Algorithm

우선순위 큐 Priority Queue

멀티 셋 Multi Set 

 

 

그리디 알고리즘 (1~2를 반복)

1. 가방의 용량이 작은 것부터 채운다.

2. 가격이 높은 보석부터 담는다.

 

 

1. 가방의 용량이 작은 것부터 채운다.

-  입력받은 가방 정보를 sort(bag.begin(), bag.end())로 가방의 용량이 작은 순서로 정렬한다.

-  for (int i = 0; i < k; i++) { ... } 로 가방의 용량이 작은 순서부터 가방 수 만큼 그리디 알고리즘을 수행한다.

-  위의 과정을 통해 가방의 용량이 작은 것부터 채워나간다. 

• 무게가 무거워 용량이 작은 가방에 들어가지 못한 보석은 용량이 큰 가방에 들어갈 수 있다. 
• 하지만 반대로 용량이 큰 가방에 들어가지 못한 보석은 작은 가방에 들어갈 수 없다.
• 따라서 가방의 용량이 작은 것부터 가방의 용량이 큰 것 순서대로 채워나가면 문제가 되지 않고 최선의 결과를 얻는다. 이를 바탕으로 그리디 알고리즘을 수행하면 올바른 결과를 얻을 수 있다. 

 

 

2. 가격이 높은 보석부터 담는다.

-  보석을 무게 순서로 정렬한다. 

-  우선순위 큐(Priority Queue)

• 우선순위 큐(Priority Queue) 선언. priority_queue<int> pQ; (이 우선순위 큐에는 보석의 가치를 담음)
• 담으려는 보석의 무게가 가방의 무게보다 작거나 같다면 현재 가방에 담을 수 있는 보석들을 pQ에 모두 담음. 이때 담을 수 있는 보석들의 가치를 담음.
• pQ에서 가장 높은 가치의 보석 하나를 answer에 더한다. (이 문제에서 " 가방에는 최대 한 개의 보석만 넣을 수 있다."라고 적혀 있다.)

 

---

 

주의할 점!!

 

정답으로 출력하는 ' 훔칠 수 있는 보석의 최대 가격 '인 answer의 자료형은 

 

int answer이 아닌 long long answer  이어야 한다!!

 

int를 사용하면 오버플로우가발생하여 long long을 사용해야 한다. 

---

 

정답 코드 -  priority_queue

 

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

struct Spec {
	int weight; int value;
};

bool Compare(Spec a, Spec b) {
	return a.weight < b.weight; // 오름차순. 무게가 가벼운 순으로 정렬
}

int n, k; // n: 보석 수, k: 가방 수
vector<Spec> gem; // 무게, 가격
vector<int> bag; // 각 가방에 담을 수 있는 최대 무게

long long answer; // 훔칠 수 있는 보석의 최대 가격

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> k;
	gem.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> gem[i].weight >> gem[i].value;
	}
	bag.resize(k);
	for (int i = 0; i < k; i++) {
		cin >> bag[i];
	}
	sort(gem.begin(), gem.end(), Compare); // 오름차순. 무게가 가벼운 순으로 정렬
	sort(bag.begin(), bag.end()); // 오름차순. 가벼운 가방 순서로 정렬

	priority_queue<int> pQ; // 가격이 높은 순으로 보석을 저장할 우선순위 큐
	int idx = 0; // 현재 보석의 인덱스
	
	for (int i = 0; i < k; i++) 
	{	
		// 현재 가방에 담을 수 있는 보석들을 우선순위 큐에 넣음
		while (idx < n && gem[idx].weight <= bag[i])
		{
			pQ.push(gem[idx].value);
			idx++;
		}

		// 우선순위 큐에서 가장 가치가 높은 보석을 꺼냄 (가방에 넣음)
		if (!pQ.empty()) {
			answer += pQ.top();
			pQ.pop();
		}
	}

	cout << answer << "\n";

	return 0;
}

 

---

 

정답 코드 - MultiSet