백준 - 1202번 : 보석 도둑 (C++)

풀이 방법 : 그리디

가방과 최대 무게라는 말에 반사적으로 DP문제인가 싶었지만 가방에 최대 한 개의 보석만 넣을 수 있다는 말을 보고 다시 생각했다 ㅋㅋㅋ

결국 입력된 보석 정보를 무게 기준으로 오름차순으로 정렬, 각 가방도 최대 무게 기준으로 오름차순 정렬을 하고 가장 작은 가방부터 채워나가는 식으로 풀어가면 된다.

채워나갈 때 중요한 것은 가방에 담을 수 있는 보석들 중에 가장 최대의 가치를 가지는 보석을 채워넣어야한다는 것이다. 여기까지는 쉽게 떠올렸으나, 단순 정렬만을 이용해 풀어보려다가 시간초과로 틀렸었다.

결국 들어갈 수 있는 보석들 중 최대 가치를 가진 보석 정보만 뽑아내면 되니 우선순위 큐를 이용하면 시간을 크게 줄일 수 있다. 게다가 이미 가방은 최대 무게 기준으로 오름차순으로 정렬을 해놨으니, 이전 가방에 들어갈 수 있던 보석들은 다음 가방에도 다 들어갈 수 있다는 것이기에 다시 처음부터 보석들을 탐색할 필요도 없다.

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

using namespace std;

struct Gem
{
	int Weight = 0;
	int Price = 0;
};

struct cmp
{
	bool operator() (const Gem& A, const Gem& B)
	{
		return A.Weight < B.Weight;
	}
};

int main()
{
	int N, K;

	cin >> N >> K;

	vector<Gem> vecGem(N);
	vector<int> vecPack(K);

	for (int i = 0; i < N; ++i)
	{
		cin >> vecGem[i].Weight >> vecGem[i].Price;
	}

	for (int i = 0; i < K; ++i)
	{
		cin >> vecPack[i];
	}

	sort(vecGem.begin(), vecGem.end(), cmp());
	sort(vecPack.begin(), vecPack.end());

	priority_queue<int> pqPrice;

	long long Sum = 0;
	int StartJ = 0;

	for (int i = 0; i < K; ++i)
	{
		for (int j = StartJ; j < N; ++j)
		{
			if (vecPack[i] >= vecGem[j].Weight)
			{
				pqPrice.push(vecGem[j].Price);
				StartJ = j + 1;
			}

			else
			{
				StartJ = j;
				break;
			}
		}

		if (pqPrice.empty())
			continue;


		Sum += pqPrice.top();
		pqPrice.pop();
	}

	cout << Sum;
}

아쉬움이 많이 남는 문제였다. 우선순위 큐를 쓸 수도 있겠다라는 생각은 했지만, 이미 정렬을 해놨으니 우선순위 큐를 굳이 써야하나 싶어서 선택지에 넣지 않았던 것이 너무 아쉬웠다. 더 빠르게 풀 수 있었는데...