[백준] 1202 보석 도둑 : C++ 풀이

접근

처음에 냅색 문제의 변형인줄 알았으나, 가방에는 보석 하나만 챙길 수 있다는 사실은 냅색과는 관련없는 개념이 사용될거라 생각했다.

보석의 크기가 30만이고, 보석을 무게순으로 정렬이 필요함을 느껴서 `우선순위 큐`를 생각했다.
아래와 같은 알고리즘을 생각해보았다.

 

1. 보석 크기 작은순 정렬
2. 가방크기 작은순 정렬
3. 만약 보석크기 > 가방크기
3-1. 가방크기 1개 pop
3-2. 그게 아니면 정답 queue에 가치값 push
4. 보석크기 1개 pop
5. 3으로 되돌아가기, 만약 가방크기가 empty가 되면 종료
6. K개만큼 위에서부터 값 합치기

 

간과한 부분

결국 다른 분들의 풀이를 참고하였다. 진짜 아깝다

내가 생각하지 못한 부분이 어디였냐면, 바로 가방 자체를 하나하나씩 훑으면서 그때마다 정답에 값을 반영해주는 부분을 생각하지 못했다.

그냥 pq 전체에 가방 개수보다 많은 보석이 push 되더라도 그냥 K 개나, 아니면 그 개수를 정확히 셀 수 있을 줄 알았다.

가방과 보석의 상관관계로는 pq에 그 개수를 정확히 계산하기에는 경험상 보았을 때, 반례가 너무 많았다.

따라서 해당 문제를 풀 때에는 가방을 직접 하나씩 순회하면서 조건에 맞는 보석들을 pq에 푸쉬하고,

pq를 통해 조건에 맞는 보석들을 정렬하여 그중 가장 큰 보석을 해당 가방에 담는 식으로 로직을 짜면 될 것이다.

 

테스트하며 사용한 직접 만든 반례 목록

1 5
1 100
2
4
6
8
10

정답 : 100

5 2
30 100
20 300
10 100
10 100
10 100
20
20

정답 : 400

5 5
1 200
1 100
1 300
1 400
1 500
1
1
2
1
1

정답 : 1500

5 5
3 100
3 100
4 100
5 100
6 100
1
2
3
4
5

정답 : 300

5 5
3 100
4 100
5 100
6 100
7 100
3
3
3
5
6

정답 : 300

소스코드

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

typedef pair<int, int> pii;

priority_queue<pii, vector<pii>, greater<pii>> gems;
priority_queue<int, vector<int>, greater<int>> bags;
priority_queue<int> pq;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, K; cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		int m, v; cin >> m >> v;
		gems.push(make_pair(m, v));
	}
	for (int i = 0; i < K; ++i) {
		int tmp; cin >> tmp;
		bags.push(tmp);
	}

	long long answer = 0;
	while (!bags.empty()) {
		int bagTop = bags.top();
		while (!gems.empty() && gems.top().first <= bagTop) {
			pq.push(gems.top().second);
			gems.pop();
		}
		if (!pq.empty()) {
			answer += pq.top();
			pq.pop();
		}
		bags.pop();
	}
	
	cout << answer;
}