[백준 알고리즘] 1202번 보석 도둑 문제풀이 c++

pos<n일때 조건을 하나 빼먹어서 13%정도에 segment 떠서 조금 헤맸다.

조건을 안 놓치도록 잘 살피자 ㅜㅜ

 

이 문제는 낮은 무게를 담을 수 있는 가방부터

가방에 담을 수 있는 것 중 최대 value를 갖는 보석을 담도록 구하면 된다.

따라서 가방(c벡터)과 보석(jw 벡터)를 무게의 오름차순으로 sort한 후,

가방i에 대해 담을 수 있는 보석의 value를 우선순위 큐에 담고

큐가 비어있지 않으면 큐의 top을 answer에 더해주고 pop해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
 	int n,k;

	cin >> n >> k;
	
	vector<pair<int,int>> jw(n);

	int m,v;
	for(int i=0; i<n; i++){
		cin >> m >> v;
		jw[i] = make_pair(m,v);
	}

	vector<int> c(k);

	for(int i=0; i<k; i++){
		cin >> c[i];
	}

	sort(c.begin(), c.end());
	sort(jw.begin(), jw.end());
	
	priority_queue<int> q;

	long long answer = 0;
	int pos = 0;
	for(int i=0; i<k; i++){
		while(pos<n &&jw[pos].first <= c[i]){
			q.push(jw[pos].second);
			pos++;
		}
		if(!q.empty()){
			answer += q.top();
			q.pop();
		}
	}
	cout << answer ;

	return 0;
}