[C++] BOJ / 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)

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

2 1
5 10
100 100
11

출력

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

10

풀이

우선순위 큐의 특징을 이용하여 풀이하였습니다.

 

보석의 무게와 가치는 pair를 통해 함께 저장해주었으며 무게를 기준으로 오름차순 정렬해주었습니다.

가방의 무게를 저장하는 배열 bag 또한 오름차순 정렬해주었습니다.

 

이후 가방의 총 개수인 k번 만큼 반복하면서 가방의 무게와 보석의 무게를 비교하여 넣을 수 있는 보석은 모두 우선순위 큐에 저장한 뒤, 우선순위 큐에서 가장 앞에 있는 값(가장 높은 가치)을 출력값에 더해주고 pop하여 다음 연산에서 제외시켜 주었습니다.

 

처음에는 우선순위 큐에 한 번에 넣는 식이 아닌 하나씩 비교하며 출력값에 더해주는 식으로 구현하였으나 중복되는 연산이 발생하며 시간초과로 인해 실패하여 결국 여러 블로그의 도움을 받았습니다.

 

참고로 출력값으로 쓰는 변수의 경우 그 값이 굉장히 커지기 때문에 long long으로 선언해 주어야 합니다.

---

#include<iostream>
#include<queue>
#include<algorithm>

#define MAX 300000

using namespace std;

int n, k;
long long ans = 0;
int bag[MAX];
pair<int, int> jewel[MAX];
priority_queue<int> pque;

void input()
{
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
		cin >> jewel[i].first >> jewel[i].second;

	for (int i = 0; i < k; ++i)
		cin >> bag[i];

	sort(jewel, jewel + n);
	sort(bag, bag + k);
}

void solve()
{
	int index = 0;

	for (int i = 0; i < k; ++i) {
		while (index < n && jewel[index].first <= bag[i])
			pque.push(jewel[index++].second);

		if (!pque.empty()) {
			ans += pque.top();
			pque.pop();
		}
	}

	cout << ans;
}

void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main()
{
	init();
	input();
	solve();

	return 0;
}