[백준]1202_보석 도둑

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

Solved

✔ 알고리즘 분류: 자료구조, 그리디 알고리즘, 정렬, 우선순위 큐
✔ 백준 인강이나 스드스 특강, 등에서 이 알고리즘의 베이직 문제(골드 문제 중에선)로 꼽는 것 같은데 오랜만에 알고리즘을 잡으니 또 새롭다.
✔ N개의 보석들은 각각 무게 M(i)와 가격 V(i)를 가지고 있다. 최대 한 개의 보석만 넣을 수 있고, 담을 수 있는 최대 무게는 각각 C(i)인 가방의 개수는 K개이다. 훔칠 수 있는 보석의 최대 가격을 구하자.
✔ 전체 가방과 전체 보석을 순회한다면 시간복잡도는 O(NK)가 나올 것이다, 그럼 N과 K의 최대값이 300,000이라서 시간초과가 나온다. 둘 중 하나의 탐색 시간을 O(logN)로 줄여보자
✔ 데이터 세팅
1. struct Jewel엔 무게, 가격 정보를 담는다.
2. multiset bag에 각 가방이 담을 수 있는 최대 무게를 저장한다.
3. jewel과 bag를 각각 정렬한다.
✔ method
1. 보석(가격 기준) 내림차순 정렬. 보석을 순회하며 알맞은 bag을 lower_bound로 찾는다.
2. 보석(무게 기준)과 가방 오름차순 정렬. 가방을 순회하며 i 번째 가방의 무게제한에 충족하는 보석을 pq에 모두 넣는다. pq는 보석(가격 기준) 내림차순 정렬 수행. 모두 넣은 후 pq.top()만 i 번째 가방에 넣고 나머지는 모두 pop().

//method 1
using namespace std;
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

struct jewel {
	int m, v;
};
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;

	vector<jewel> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i].m >> a[i].v;
	sort(a.begin(), a.end(), [](jewel u, jewel v) {
		return u.v > v.v;
		});

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

	long long ans = 0;
	for (int i = 0; i < n; i++) {
		auto it = bag.lower_bound(a[i].m);
		if (it != bag.end()) {
			ans += a[i].v;
			bag.erase(it);
		}
	}
	cout << ans << '\n';
}

//method 2
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 300000;

int N, K;
int bag[MAX];
pair<int, int> jewelry[MAX];
priority_queue<int> pq; //maxHeap 사용

int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0); //cin 실행속도 향상
	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> jewelry[i].first >> jewelry[i].second;

	for (int i = 0; i < K; i++)
		cin >> bag[i];

	//보석(무게 기준)과 가방 오름차순 정렬
	sort(jewelry, jewelry + N);
	sort(bag, bag + K);

	long long result= 0;
	int idx = 0;

	//무게제한이 낮은 가방부터 최대한 비싼 보석을 넣는 방법
	for (int i = 0; i < K; i++){
		//i 번째 가방의 무게제한에 충족하는 보석 다 넣음
		while (idx < N && jewelry[idx].first <= bag[i])
			pq.push(jewelry[idx++].second);
		//pq의 루트에는 현재 기준 제일 비싼 보석이 들어있음
		if (!pq.empty()) {
			result += pq.top();
			pq.pop();
		}
	}
	cout << result << "\n";
	return 0;
}