[Gold 2] 1202 보석 도둑

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

1202번: 보석 도둑

 

이 문제는 그리디 알고리즘을 사용해야한다.

문제를 해결할 수 있는 방법은 다음과 같다.

보석을 무게 순서로 정렬하고, 가방에 담을 수 있는 보석의 최대 무게도 오름 차순으로 정렬한다.

 

위 과정을 거치면 가방에 담을 수 있는 무게를 가진 보석을 순서대로 뽑을 수 있다.

이후 우선순위 큐에 보석의 무게를 넣게 된다면 큐에는 가장 무거운 보석을 top에 위치시킬 수 있다.

이러면 가방에 넣을 수 있는 보석 중 가장 무거운 보석을 찾을 수 있을 것이다.

 

위 과정을 생각해보면, 큐에 같은 무게를 가진 보석이 2개 이상 존재할 가능성이 생길 수 있다.

따라서 보석이 담긴 배열을 순회할 때 중복해서 순회하지 못하게 해야한다.

이 과정은 배열 순회 시간도 줄여줄 뿐만 아니라 앞서 설명한 문제점도 해결해 줄 수 있다.

이 문제를 해결하기 위해 index 변수를 통해 배열을 2번 순회하지 못하게 한다.

 

또다른 문제점으로는 배열을 2번 순회하지 않는 것은 좋지만 조건에 맞는 보석을 꺼내지 못할 가능성에 대해 생각해 볼 수 있다.

이는 보석과 가방의 무게가 담긴 배열을 정렬하는 과정을 통해 제거되는 문제이다.

정렬을 통해 무게 순서대로 배열의 요소가 담겨있으므로 더 무거운 무게를 담을 수 있는 가방은 이전에 탐색한 보석도 사용할 수 있다.

따라서 우선순위 큐를 통해 가장 무거운 보석을 꺼내기만 하면 된다.

 

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

int N, K;
long long value = 0;
priority_queue <int, vector<int>>q;
vector<int> bag;
vector<pair<int, int>> jewerly;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	int M, V;
	for (int i = 0; i < N; i++) {
		cin >> M >> V;
		jewerly.push_back({ M,V });
	}

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

	int index = 0;
	for (int i = 0; i < bag.size(); i++) {
		while (index < N && bag[i] >= jewerly[index].first) {
			q.push(jewerly[index].second);
			index++;
		}
		if (!q.empty()) {
			value += q.top();
			q.pop();
		}
	}
	cout << value<<'\n';
}