백준 1202번 보석 도둑

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

사용한 알고리즘: priority_queue..?


 보석들의 무게, 가치 가 주어지고, 담을 수 있는 무게가 각각 다른 (같을 수 있다.) 가방들이 주어졌을 때 훔칠 수 있는 보석들의 가치의 합의 최대를 구하는 문제였습니다.

문제 풀이는 다음과 같습니다.
(1) 보석의 <무게, 가치> 를 pair로 저장합니다. 이후 가치가 큰게 위로 오게끔 pq를 만들어 줍니다. 가방은 multiset을 이용하여 저장해줍니다. set이 아닌 multiset을 쓰는 이유는 담을 수 있는 무게가 같은 가방이 있을 수 있기 때문에 해당 가방의 개수를 세어주기 위함입니다.

(2) pq에서 차례로 보석을 꺼내면서 해당 보석을 담을 수 있는 가방을 lower_bound 함수를 사용하여 multiset에서 뽑습니다. 이때 해당 가방을 사용하였다는 것을 int 배열을 통해 사용할 때마다 세어주었습니다. 해당가방의 multiset의 값 ( 입력받은 가방의 수) 이 int 배열에 저장된 값 ( 사용 횟수 ) 보다 클 경우(초과) 인 경우에만 해당 가방을 사용할 수 있습니다.

(3) 보석을 해당 가방을 사용할 수 없다면 그보다 큰 (lower_bound를 사용하였으므로 해당 iterator보다 큰 가방들은 모두 해당 가방보다 많은 무게를 담을 수 잇다.) 가방들을 차례로 보며, 넣을 수 있는 가방에 보석을 넣습니다. 보석은 가치가 큰 순으로 pq에서 뽑기 때문에 들어갈 수 있는 가방에 무조건 넣어주면 됩니다.

(4) 가방을 모두 사용해 주거나 보석을 pq에서 모두 꺼낸 경우 위 과정을 끝내줍니다.


문제에서 주의할 점은 같은 가방이 여러개 들어올 수 있는 점을 의식하는 것이었습니다.
(이를 위해 set이 아닌 multiset을 사용하였습니다.)

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int> // pair<무게, 가치>
	// 보석 가치 큰순으로 pq
	int N, K;
	struct cmp{
	bool operator()(const pii &t, const pii &u){
	// 가치가 같으면 무게 작은게 위로
	if(t.second==u.second) return t.first>u.first;
	// 가치 큰게 위로
	return t.second < u.second;
	}
	};
	priority_queue<pii , vector<pii>, cmp> jewel;
	multiset<int> Bag;
	// 똑같은 가방 여러개 들어올 수 있음!
	int BagUsed[3000001];
	long long ans;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> K;
	for (int i = 0; i < N; ++i){
	int m, v;
	cin >> m >> v;
	jewel.push(pii(m,v));
	}
	for (int i = 0; i < K; ++i){
	int num;
	cin >> num;
	Bag.insert(num);
	}
	int cnt = 0; // 가방 개수 확인용
	while(!jewel.empty()){
	pii now = jewel.top();
	jewel.pop();
	// lower_bound 함수 활용 -> now.first (보석 무게) '이상' 값 찾아줌
	auto iter = Bag.lower_bound(now.first);
	// 보석 무게 이상 값 없으면 iter == Bag.end();
	if(iter!=Bag.end() && BagUsed[*iter]<Bag.count(*iter)){
	BagUsed[*iter]++;
	if(BagUsed[*iter]==Bag.count(*iter)) Bag.erase(*iter);
	cnt++;
	ans+=now.second;
	}
	// 가방 다쓰면 끝
	if(cnt==K) break;
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 1202.cpp hosted with ❤ by GitHub