[백준] 1202 보석 도둑 (C++)

백준 1202 보석 도둑 문제
백준 1202 보석 도둑 소스코드

📄 문제 설명

Problem

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

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

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

Input

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
다음 N개 줄 : 각 보석의 정보 Mi와 Vi (0 ≤ Mi, Vi ≤ 1,000,000)
다음 K개 줄 : 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

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

Output

첫째 줄 : 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

Example Input 1

2 1
5 10
100 100
11

Example Output 1

10

Example Input 2

3 2
1 65
5 23
2 99
10
2

Example Output 2

164

📝 문제 해설

이 문제는 주어진 보석의 무게와 가치를 고려해 주어진 가방 안에 최대 하나의 보석을 넣어
최대 가치를 만들어 내는 문제이다.

우선순위 큐를 활용해 문제를 해결하였다.

문제 해결 순서

1. 보석의 무게(weight)와 가치(value)를 가지고 있는 Jewerly 구조체 생성
2. Jewerly type의 벡터 jew와 가방의 정보를 가지고 있는 벡터 bag 선언

3. jew는 무게를 기준으로, bag은 수용크기 기준으로 오름차순 정렬

4. 가치가 높은 보석이 우선순위를 갖는 우선순위 큐(pq) 생성

5. bag을 순서대로 탐색하며 수용크기보다 작거나 같은 보석을 while문으로 순회하며 pq에 삽입
  (수용 크기보다 더 큰 보석을 만나면 while문을 탈출하게 된다.)
6. pq의 top에는 무게가 수용크기보다 작거나 같은 보석 중 가치가 가장 큰 보석.
7. pq top 삭제

8. jew와 bag 벡터가 empty()가 아닐 때까지 5 ~ 7 반복

Input Example 2를 예시로 들어 설명하면,

1. bag[0] : 1
	2. jew[0] : 1 ➡ 같으므로 pq에 삽입
 	   jew[1] : 2 ➡ while문 탈출
	3. result += pq.top() //result += 65 ➡ 수용 가능한 보석 중 가치가 가장 큰 보석
	4. pq.pop() ➡ 사용한 보석은 다시 쓸 수 없으므로 pq에서 삭제

5. bag[1] : 10
	6. jew[1] : 2 ➡ 10보다 작으므로 pq에 삽입
	7. jew[2] : 5 ➡ 10보다 작으므로 pq에 삽입
	8. result += pq.top() //result += 99 ➡ 수용 가능한 보석 중 가치가 가장 큰 보석
	9. pq.pop() ➡ 사용한 보석은 다시 쓸 수 없으므로 pq에서 삭제

10. bag이 empty()상태 이므로 탐색 종료

∴ result = 164

</> Source Code

#include <bits/stdc++.h>

using namespace std;

struct Jewerly{
	int weight;
	int value;
};

bool weightComp(const Jewerly& a, const Jewerly&b){
	return a.weight < b.weight;
}

struct valueComp{
	bool operator()(const Jewerly& a, const Jewerly& b){
		return a.value < b.value;
	}
};

int main(){	
	int n, k;
	scanf("%d %d", &n, &k);
	
	vector<Jewerly> jew;
	vector<int> bag;
	
	for(int i = 0; i < n; i++){
		int m, v;
		scanf("%d %d", &m, &v);		
		jew.push_back({m, v});
	}
	
	for(int i = 0; i < k; i++){
		int c;
		scanf("%d", &c);		
		bag.push_back(c);	
	}
		
	sort(jew.begin(), jew.end(), weightComp);
	sort(bag.begin(), bag.end());
	
	long long int result = 0;
	priority_queue<Jewerly, vector<Jewerly>, valueComp> pq;
   
	int bagIdx = 0;
	for(int i = 0; i < bag.size(); i++){
		while(bagIdx < n & jew[bagIdx].weight <= bag[i]){
			pq.push(jew[bagIdx]);
			bagIdx++;
		}
		
		if(!pq.empty()){
			result += pq.top().value;
			pq.pop();
		}
	}	
	
	printf("%lld", result);
	
	return 0;
}