1202 - 보석 도둑

문제

코드

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

int n,m,v,k,c;
vector<pair<ll,ll>>d;
vector<ll> b;
ll ret;

int main(){
	cin >> n >> k;
	
	for(int i = 0; i <n; i++){
		cin >> m >> v;
		d.push_back({m,v});
	}
	
	for(int i = 0; i < k; i++){
		cin >> c;
		b.push_back(c);
	}
	
	sort(d.begin(), d.end());
	sort(b.begin(), b.end());
	priority_queue<ll> pq;
	
	int j = 0;
	for(int i = 0; i < k; i++){
		while(j < n && d[j].first <= b[i]){
		pq.push(d[j].second);
		j++;
		}
	if(pq.size()){
			ret += pq.top();
			pq.pop();
		}
	}
	cout << ret << '\n';
}

풀이

보석의 무게, 가방의 용량을 오름차순으로 정렬한다.
아무렇게나 되어 있으면 담는 행위를 할 때 훨씬 복잡해지기 때문이다.
기준은 좀 더 효율적이라 생각되는 가방을 기준으로 잡았다.
int i = 0부터 k(가방의 갯수)까지 하나씩 검사하는데
그때 보석은 n(보석의 갯수)까지 하나씩 보석의 무게가 가방의 용량보다 작으면 일단 다 담는다.
그렇게 가방 하나를 다 탐색하고 젤 가격이 높은 것을 ret에 담고 다음 가방으로 넘어간다.

결과

후기

솔직히 골드 2라고 해서 엄청 쫄았다. 실제로 처음에 너무 간단하게 구현했으나 틀려서 계속 꼬아서 생각하다보니 풀기 어려웠다. 우선순위 큐를 처음 써봤는데 아직은 어색하고 얼른 자주 써서 익숙해져야겠다는 생각이 들었다. 유용하게 쓸 수 있을듯 하다.
뭔가 쉬운듯 어려운듯 아리까리한 문제 같다.