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

JG's Development Blog·2022년 8월 31일
0

코딩 문제풀이

목록 보기
14/32

링크


https://www.acmicpc.net/problem/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)

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

출력


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

풀이


맨처음에 우선순위 큐 없이 풀 수 있을 것이라 생각했다.
그래서 보석의 정보를 가격을 기준으로 정렬하고 가장 적게 담을 수 있는 가방부터 검사하였다.
가격이 높은 보석부터 담을 수 있는 무게면 바로 담는 알고리즘을 세웠다.

그러나 문제가 있었는데 현재 보석의 정보가 가격을 기준으로 정렬되어있기에 무게는 무작위로 섞여있다.
이는 비효율적인 분배를 초래하였다. 즉, 무조건 가격이 높은 보석을 먼저 담게 되면 그다음 가방은 아무것도 담지 못하는 상황이 일어날 수 있는것이다.

따라서 우선순위 큐를 이용하여 담을 수 있는 모든 보석에서 하나씩 골라내야만 한다.

또한 결과값이 int가 표현할 수 있는 정수를 넘어설 수 있음에 주의해야한다.

코드


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

int main() {
	int N;
	int K;
	cin >> N >> K;

	vector<pair<int, int>> v;
	int a, b;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		v.push_back({ a,b });
	}
	sort(v.begin(), v.end());

	vector<int> bag;
	int tmp;
	for (int i = 0; i < K; i++) {
		cin >> tmp;
		bag.push_back(tmp);
	}
	sort(bag.begin(), bag.end());

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

	cout << result << "\n";

	return 0;
}

profile
왕왕왕초보

0개의 댓글