[그리디 알고리즘] 보석 도둑

예제 입력 1

3 2

1 65

5 23

2 99

10

2

예제 출력 1

164

 

- 두 가지 방법으로 풀이가 가능하다.

1) 각각의 보석을 기준으로, 보석이 어떤 가방에 들어가면 좋을까? 가격이 높은 순으로 들어갈 수 있는 가장 작은 가방에 넣고 그 가방을 지운다.

2) 각각의 가방을 기준으로, 어떤 보석이 들어가면 좋을까??

 

[ 풀이 1) ]

#include <stdio.h>
#include <algorithm>
#include <set>
#include <vector>

const int MAX_SIZE = 300000;

using namespace std;

class Jewel
{
public:
	int m; // 무게
	int v; // 가격
};

multiset<int> bag;

int N;
int K;

int main(void)
{
	scanf("%d %d", &N, &K);

	vector<Jewel> j(N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &j[i].m, &j[i].v);
	}

	for (int i = 0; i < K; i++)
	{
		int weight;
		scanf("%d", &weight);
		bag.insert(weight);
	}

	sort(j.begin(), j.end(), [](Jewel u, Jewel v) {
		return u.v > v.v;
	});

	long long ans = 0;
	for (int i = 0; i < N; i++)
	{
		auto it = bag.lower_bound(j[i].m); // BST 자료구조로 하면 logK에 할 수 있다. (K = 가방 개수)

		if (it != bag.end())
		{
			ans += j[i].v;
			bag.erase(it);
		}
	}

	printf("%lld\n", ans);

	return 0;
}

 

 

[ 풀이 2) ]

#include <queue>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

class Jewel
{
public:
	int m, v;
	int w; // w = 1이면 가방을 의미

	Jewel()
	{
		m = v = w = 0;
	}
};
int N, K;

int main(void)
{
	scanf("%d %d", &N, &K);
	vector<Jewel> j(N + K);

	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &j[i].m, &j[i].v);
	}

	for (int i = 0; i < K; i++)
	{
		scanf("%d", &j[i + N].m);
		j[i + N].w = 1;
	}

	sort(j.begin(), j.end(), [](Jewel u, Jewel v) {
		if (u.m == v.m) return u.w < v.w; // 보석이 가방보다 앞에
		return u.m < v.m;
	});

	priority_queue<int> q;
	long long ans = 0;

	for (auto& p : j)
	{
		if (p.w == 0) // 보석이면 그 가격을 넣는다.
			q.push(p.v);
		else
		{
			if (!q.empty()) // 가방이면
			{
				ans += (long long)q.top(); // 현재까지 최대가격 보석
				q.pop();
			}
		}
	}

	printf("%lld\n", ans);
	return 0;
}