그리디 (BOJ 1202 보석 도둑)

문제

보석 도둑

알고리즘

1. 보석과 가방을 오름차순으로 정렬
2. 가방을 기준으로 탐색을 진행
3. priority_queue에 보석을 넣으며 가방 별로 넣을 수 있는 가장 높은 밸류를 구함
4. 3에서 구한 값들을 더함

코드

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll N, K, ret = 0;
ll visited[300004] = {0,};

vector<ll> bag;
vector<pair<ll,ll>> jewelry;
priority_queue<ll> pq; // val


void run(){
	cin >> N >> K;
	for(int i=0; i<N; i++){
		ll weight, value;
		cin >> weight >> value;
		
		jewelry.push_back({weight, value});
	}
	
	sort(jewelry.begin(), jewelry.end());
	
	for(int i=0; i<K; i++){
		ll limit;
		cin >> limit;
		bag.push_back(limit);
	}
	
	sort(bag.begin(), bag.end());
	
	
	
	int j=0;
	
	for(int i=0; i<bag.size(); i++){
		
		while(j < N && jewelry[j].first <= bag[i]) 
			pq.push(jewelry[j++].second);
		
		if(!pq.empty()){
			ret += pq.top();
			pq.pop();
		}
	}

	cout << ret << "\n";
}


int main(){
	run();
	return 0;
}

후기

처음으로 막혔던 그리디 문제.

가방과 보석을 구분해서 탐색하는 발상까지는 도달했지만
그 기준점을 보석으로 잡고 구상하니 코드가 뺑뺑 돌아버렸다..
결국 더이상의 시간 낭비는 무의미하다고 생각돼 답안지를 보고 해결.

배워야할 게 너무 많아서 압사 당하는 기분이지만..
막연하게 무서워하기보단 글이라도 끄적이는게 그나마 낫겠지라는 생각
하다보면 되겠..지?