백준/1202번/보석 도둑/골드2

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

문제 설명

Site: Baekjoon
Number: 1202
Category: Greedy
Rank: Gold 2

보석들의 무게와 가격이 주어지고, 보석을 단 한개만 넣을 수 있는 가방의 무게 들이 주어졌을 때, 담을 수 있는 보석의 최대 가격을 구하는 문제입니다.

구하는 방법은 쉽지만, 푸는 방식이 오래걸린다면 시간초과가 발생하여 시간 복잡도를 잘 고려해야 하는 문제입니다.

문제 풀이

보석을 가격 기반으로 내림차순으로 정렬하고, 하나씩 꺼내며 넣을 수 있는 가방 중 가장 작은 크기에 가방에 넣어서 문제를 해결할 수 있습니다.

보석은 우선 순위 큐를 통해 정렬하였으며, 가방은 lower_bound를 통해 넣을 수 있는 크기 중 가장 작은 걸 가져오기 위해 Multiset을 사용하였습니다.

Multiset 사용이유?
std::lower_bound는 O(N)의 시간 복잡도를 가지지만, set과 map 등의 lower_bound는 O(log N)의 시간 복잡도를 가져 multiset을 사용합니다.

#include <iostream>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

#define PII pair<int, int>

// 보석 가격 기반 정렬
struct cmp
{
	bool operator()(PII a, PII b)
	{
		return a.second < b.second;
	}
};

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, K;
	cin >> N >> K;

	priority_queue<PII, vector<PII>, cmp> Jewels;
	multiset<int> Bags;

	for(int i = 0; i < N; i++)
	{
		int weight, price;
		cin >> weight >> price;

		Jewels.emplace(weight, price);
	}

	for(int i = 0; i < K; i++)
	{
		int S;
		cin >> S;

		Bags.insert(S);
	}

	long long total = 0;

	while(!Jewels.empty() && !Bags.empty())
	{
		int weight = Jewels.top().first;
		int price = Jewels.top().second;
		Jewels.pop();

		auto iter = Bags.lower_bound(weight);

		if(iter != Bags.end())
		{
			total += (long long)price;
			Bags.erase(iter);
		}
	}

	cout << total;

	return 0;
}