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

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

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 가 30만 번이라 O(N*K)으로 갈 수 있어서 안 되는 것 같았다.

그래서 보석의 가격을 내림차순으로 과 가방의 크기를 오름차순으로 정렬을 해서 비싼 보석을 먼저 넣을 수 있는 가방에 넣는 방식을 활용했지만 이 방식은 틀렸다고 나왔다. 이 방법이 왜 틀린지는 아직 알아내지 못했다. 하지만 이 방법 역시 O(N*K)의 시간이 걸리므로 안될 것 같았다.

그래서 알아낸 알맞은 방법은 두 배열 모두 무게의 오름차순으로 정렬을 한 다음 i번 째 가방에 넣을 수 있는 모든 보석을 PQ 에 삽입한 후 그 가방에 PQ의 top에 있는 보석을 추가하는 방식이었다. 이렇게 되면 정렬을 한 후 O(N+K) 시간 안에 문제를 풀 수 있게 된다.

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

int N, K, C;
pair <int, int> arr[300001];
int bag[300001];
bool vis[300001] = { false };
long long ans = 0;
pair<int, int> item;

long long solve() {
	long long res =0;
	int idx = 0;
	priority_queue <int> pq;
	for (int i = 0; i < K; i++) {
		while (idx < N && bag[i] >= arr[idx].first) {
			pq.push(arr[idx++].second);
		}
		if (!pq.empty()) {
			res += pq.top();
			pq.pop();
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	for (int i = 0; i < K; i++) {
		cin >> bag[i];
	}
	sort(arr, arr + N);
	sort(bag, bag + K);
	cout << solve();
}

---

처음에 봤을 때 냅색보다 쉬운 문제 인것 같다고 인식해서 인지 생각을 조금만 하고 바로 코드에 손을 대 버렸다. 삼성 특강에서 가장 크게 느낀 게 생각을 조금 더 하면 코드에 시간을 많이 줄일 수 있다는 것인데 그걸 바로 안 해버렸다! 지금이라도 다시 한번 느꼈으니 안 그러길 바란다..