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

문제 링크: https://www.acmicpc.net/problem/1202

 

배낭 문제(knapsack problem)의 변형판입니다. DP를 사용할 필요가 없습니다. 그리디로 풀면 됩니다.

한 가방에 보석 한개밖에 못넣기 때문에 문제가 간단합니다.

 

 

일단 가방은 무게 오름차순으로, 보석은 가격 내림차순으로 정렬합니다.

가장 값나가는 보석부터 차례대로 넣습니다. 어느 배낭에 넣을지 결정하는 것이 문제인데요, 넣을 수 있는 가방 중에 용량이 가장 작은 걸 고르면 됩니다.

 

여기서 감이 오실텐데요, 이분탐색을 쓰면 됩니다.

lower_bound를 사용해 적당한 가방을 골라 넣습니다. 조건에 해당하는 가방이 없는 경우 (=용량이 제일 큰 가방보다 보석 무게가 더 무거운 경우) 체크해서 빼줍니다. 사용한 가방은 가방 목록에서 뺍니다.

 

가방 목록의 자료구조는 뭘 써야 할까요? vector는 erase할 때마다 재배열을 해줘야 하니 O(n)의 시간이 걸립니다. 그래서 set을 쓰면 삭제가 O(log n)이니 쓰면 될 것 같은데, 같은 용량을 가진 가방이 여러개 나올 수 있으니 multiset을 사용하면 됩니다.

multiset에서 lower_bound를 쓸 땐 multiset의 메소드 lower_bound를 써야 O(log n)의 시간이 걸립니다. lower_bound 함수를 쓰면 O(n)의 시간이 걸립니다. 그럼 이분탐색이 아니고 선형탐색이죠? iterator가 random access가 가능할 때만 O(log n)이 보장됩니다.

map, set, multiset 자료구조에서 이분탐색을 할 땐 꼭 메소드의 lower_bound, upper_bound를 사용해주세요.

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int n, k;
	cin >> n >> k;

	vector<pair<int, int>> jewels(n);	// cost(-), weight
	for (auto& p : jewels) {
		cin >> p.second >> p.first;
		p.first = -p.first;
	}

	multiset<int> knapsacks;
	for (int i = 0; i < k; ++i) {
		int in; 
		cin >> in;
		knapsacks.insert(in);
	}

	sort(jewels.begin(), jewels.end());

	ll sum = 0;
	for (auto [cost, weight] : jewels) {
		cost = -cost;

		auto it = knapsacks.lower_bound(weight);
		if (it != knapsacks.end()) {
			sum += cost;
			knapsacks.erase(it);
			if (knapsacks.empty()) break;
		}
	}
	cout << sum << '\n';
	
	return 0;
}