보석 도둑(Greedy)

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

1202번: 보석 도둑

 

무게 M과 가격 V인 보석과 허용 무게가 C인 배낭들이 여러개 주어진다.

이때 각 배낭에 보석을 한 개씩만 넣어서 넣은 보석들의 가치가 최대가 되도록 해야한다.

 

해당 문제는 각 상황마다 최대 가치를 지니는 보석을 최대한 적은 허용량을 갖는 배낭에 넣는 방법으로

그리디하게 풀 수 있다.

 

하지만 모든 보석에 대하여 모든 배낭을 선형탐색하게 되면 N^2의 시간이 소요되므로 시간초과에 걸리게 된다.

보석을 기준으로 배낭을 찾는 것이 아닌, 배낭을 기준으로 보석을 찾도록 해야함.

 

1. 보석은 무게를 기준으로 오름차순, 배낭도 허용량을 기준으로 오름차순 정렬을 해준다.

2. 가장 앞의 배낭을 선택한다(현재 허용량이 가장 적은 배낭).

3. 해당 배낭에 넣을 수 있는 보석을 전부 우선순위 큐에 넣어준다(우선순위 큐의 기준은 보석의 가치).

4. 우선순위 큐에서 가장 위에 있는 보석이 현재 배낭에 넣을 수 있는 가장 가치가 높은 보석이다.

5. 우선순위 큐의 top의 가치를 결과에 추가하고 pop한다.

6. 우선순위 큐를 유지한채 모든 배낭에 대해 2~5번의 과정을 시행한다.

 

이렇게 되면 배낭과 보석 각각에 대한 선형탐색이 이루어지므로 N^2이 아닌 NlogN의 시간복잡도로 해결할 수 있다.

(탐색 자체는 N+K지만 정렬에 NlogN 시간이 소요됨)

 

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

class Jewel
{
public:
	int m;
	int v;
	Jewel(int m, int v)
	{
		this->m = m;
		this->v = v;
	}
	bool operator<(const Jewel j) const
	{
		return this->m < j.m;
	}
};

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

	int jc, bc;
	cin >> jc >> bc;

	int cmd;

	vector<Jewel> jv;
	cmd = jc;
	while (cmd--)
	{
		int m, v;
		cin >> m >> v;
		jv.push_back(Jewel(m, v));
	}

	vector<int> bv;
	cmd = bc;
	while (cmd--)
	{
		int c;
		cin >> c;
		bv.push_back(c);
	}
	sort(jv.begin(), jv.end());
	sort(bv.begin(), bv.end());

	int jv_idx = 0;
	long long ret = 0;
	priority_queue<int> pq;
	for (int i = 0; i < bc; i++)
	{
		// 현재 배낭의 무게
		int curb = bv[i];
		// 현재 배낭의 무게보다 작은 보석을 pq에 전부 삽입
		while (jv_idx < jc && jv[jv_idx].m <= curb)
		{
			pq.push(jv[jv_idx].v);
			jv_idx++;
		}
		// pq가 비어있지 않다면 가장 위의(가치 가장 높음) 보석을 현재 배낭에 넣음
		if (!pq.empty())
		{
			ret += pq.top();
			pq.pop();
		}
		// 해당 과정을 모든 배낭에 대해서 반복
	}

	cout << ret << '\n';
}