[백준 1202 - 골드 2] 보석 도둑.cpp

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

1202번: 보석 도둑

 

	#define _CRT_SECURE_NO_WARNINGS
	#include <iostream>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct Gem
	{
	int weight, value;
	};
	bool comp(const Gem& lhs, const Gem& rhs)
	{
	return lhs.weight < rhs.weight;
	}
	int N, K;
	int bag[300000];
	Gem gem[300000];
	void Input()
	{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++)
	{
	scanf("%d %d", &gem[i].weight, &gem[i].value);
	}
	for (int i = 0; i < K; i++)
	{
	scanf("%d", &bag[i]);
	}
	}
	void Sol()
	{
	priority_queue<int> pq;
	long long int total_value = 0;
	int gem_idx = 0;
	sort(gem, gem + N, comp);
	sort(bag, bag + K);
	for (int bag_idx = 0; bag_idx < K; bag_idx++)
	{
	int max_weight = bag[bag_idx];
	while (gem_idx < N)
	{
	if (max_weight < gem[gem_idx].weight) break;
	pq.push(gem[gem_idx++].value);
	}
	if (pq.empty() == false)
	{
	total_value += pq.top();
	pq.pop();
	}
	}
	printf("%lld", total_value);
	}
	int main()
	{
	Input();
	Sol();
	}
	/* 첫 번째 풀이
	#define _CRT_SECURE_NO_WARNINGS
	#include <stdio.h>
	#include <algorithm>
	const int MAX = 300000;
	using namespace std;
	struct Gem
	{
	int M, V;
	};
	struct Bag
	{
	int C, V;
	};
	int N, K;
	Gem gem[MAX];
	Bag bag[MAX];
	bool compare_gem(const Gem& lhs, const Gem& rhs)
	{
	if (lhs.V == rhs.V)
	{
	return lhs.M < rhs.M;
	}
	return lhs.V > rhs.V;
	}
	bool compare_bag(const Bag& lhs, const Bag& rhs)
	{
	return lhs.C < rhs.C;
	}
	void Input()
	{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++)
	{
	scanf("%d %d", &gem[i].M, &gem[i].V);
	}
	for (int i = 0; i < K; i++)
	{
	scanf("%d", &bag[i].C);
	}
	}
	void Sol()
	{
	long long int sol = 0;
	sort(gem, gem + N, compare_gem);
	sort(bag, bag + K, compare_bag);
	for (int i = 0; i < K; i++)
	{
	for (int j = 0; j < N; j++)
	{
	if (gem[j].V == -1) continue;
	if (bag[i].C >= gem[j].M)
	{
	sol += gem[j].V;
	gem[j].V = -1;
	break;
	}
	}
	}
	printf("%d", sol);
	}
	int main()
	{
	Input();
	Sol();
	return 0;
	}
	*/

view raw <1202> 보석 도둑.cpp hosted with ❤ by GitHub

문제의 이해 자체는 크게 어렵지 않았다.

아래 주석처리가 되어있는 부분이 처음 풀이.

가방에 들어갈 수 있는 무게에 따라 가방을 정렬 후,

순차적으로 가방에 보석을 넣어주었다.

당연하게도 시간 초과.

 

그 후, 우선순위 큐를 이용한 풀이로 통과했다.

풀이의 컨셉은 다음과 같다.

 

우선순위 큐에 보석을 넣고, 보석의 가치에 따라 정렬한다.

그 다음, 높은 가치인 보석을 가방에 넣어주면된다.

 

여기서 생각해봐야 할 부분은,

"어떤 보석을 우선순위 큐에 넣어줄 것인가?"

 

여기서 힌트는,

허용무게가 적은 가방에 먼저 보석을 넣어줘야 한다는 것이다.

 

따라서, 가방과 보석을 무게 오름차순으로 정렬한다.

그 뒤, 첫번째 가방에 들어갈 수 있는 보석들까지 우선순위 큐에 넣는다.

정렬이 되어있기 때문에, 가방의 허용무게 이하인 보석까지 넣으면 된다.

그리고 우선순위 큐의 가장 높은 보석을 가방에 넣고,

다음 가방의 허용무게와 보석의 무게를 비교하여 우선순위 큐에 넣는다.

다시 우선순위 큐의 가장 높은 보석을 가방에 넣는다.

 

이를 모든 가방에 반복하면 끝.

 

우선순위 큐를 잘 써보지 않았는데,

우선순위 큐의 장점을 확실히 느낄 수 있었던 문제.