[ C++ 백준 1202 ] 보석 도둑

---

일단 문제를 풀어보기로 했다.

일단 한 번 코드를 작성해보았는데, 문제가 많았다.

#include <iostream>
#include <algorithm>

using namespace std;

struct Gem
{
public:
	Gem() : weight(0), price(0) {};
	Gem(int weight, int price) : weight(weight), price(price) { };
	~Gem() {};

public:
	int weight;
	int price;

	bool operator>(const Gem& gem)
	{
		return price > gem.price;
	}
};

Gem gems[300000];
int bagWeight[300000];	//가방에 담을 수 있는 최대 무게
bool visited[300000];

int gemCnt, bagCnt;
// N이 보석의 정보를 담는 개수
// K가 가방에 담을 수 있는 최대 무게

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	int gemWeight, gemPrice;
	 
	cin >> gemCnt >> bagCnt;
	for (int i = 0; i < gemCnt; ++i)
	{
		cin >> gemWeight >> gemPrice;
		gems[i] = { gemWeight, gemPrice };
	}
	for (int i = 0; i < bagCnt; ++i)
		cin >> bagWeight[i];

	// 가격이 가장 높은 걸 기준으로
	// 제일 무게가 적게 나가는 걸로
	sort(gems, gems + gemCnt,
		[](Gem a, Gem b) -> bool
		{
			return a > b;
		});
	sort(bagWeight, bagWeight + bagCnt);

	int answer = 0;
	for (int i = 0; i < gemCnt; ++i)
	{
		//가격이 비싼 보석부터 담는다.
		for (int j = 0; j < bagCnt; ++j)
		{
			if (visited[j]) continue;
			if (bagWeight[j] < gems[i].weight) continue;

			visited[j] = true;
			answer += gems[i].price;
			break;
		}
	}

	cout << answer;
}

시간 초과가 난 첫번째 코드다.

 

이중 포문으로 인해 시간도 매우 오래걸리고, 코드에서도 문제가 좀 많다.

그리고 우선순위 큐를 이용해서 문제들을 해결해보기로 했고, 코드를 작성했다.

 

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

using namespace std;

struct Gem
{
public:
	Gem() : weight(0), price(0) {};
	Gem(int weight, int price) : weight(weight), price(price) { };
	~Gem() {};

public:
	int weight;
	int price;

	bool operator<(const Gem& gem)
	{
		return weight < gem.weight;
	}
};

Gem gems[300000];
int bagWeight[300000];	//가방에 담을 수 있는 최대 무게
priority_queue<int, vector<int>, less<int>> pq;

int gemCnt, bagCnt;
// N이 보석의 정보를 담는 개수
// K가 가방에 담을 수 있는 최대 무게

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	int gemWeight, gemPrice;
	 
	cin >> gemCnt >> bagCnt;
	for (int i = 0; i < gemCnt; ++i)
	{
		cin >> gemWeight >> gemPrice;
		gems[i] = { gemWeight, gemPrice };
	}
	for (int i = 0; i < bagCnt; ++i)
		cin >> bagWeight[i];

	sort(gems, gems + gemCnt);
	sort(bagWeight, bagWeight + bagCnt);

	int idx = 0;
	long long answer = 0;
	//무게가 낮은 가방부터 체크
	for (int i = 0; i < bagCnt; ++i)
	{
		// 무게가 낮은 보석부터 체크
		while(idx < gemCnt 
			&& bagWeight[i] >= gems[idx].weight)
		{
			pq.push(gems[idx++].price);
		}

		if (pq.empty()) continue;

		answer += pq.top();
		pq.pop();
	}

	cout << answer;
}

해결한 코드이다.

 

answer를 long long 변수로 변경했고,

풀이 방식을 살짝 바꿨다.