백준 1202번. 보석 도둑(c++) / Greedy

이러한 유형은 매우 자주 접했던 그리디 유형이다.

보석의 정보와 가방의 정보를 각각 저장하고

보석은 무게를 기준으로 정렬, 가방도 정렬한다.

그리고 가방을 기준으로 가장 높은 가치를 가지고 있는 보석을 담는다. -> 우선순위큐 사용

 

코드 첨부

// 보석 도둑
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n, k, m, v;
pair<int, int> jewelry[300001];
int bag[300001] = {0, };
priority_queue<int> pq;
long long final = 0;
 
int main()
{
    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);
 
    int idx = 0;
 
    // 가방을 기준으로(무게)
    for(int i=0; i<k; i++){
        while(idx<n && jewelry[idx].first<=bag[i]){
            pq.push(jewelry[idx++].second);
        }
 
        if(!pq.empty()){
            final += pq.top(); // root에 있는 값을 더해준다.
            pq.pop();
        }
    }
 
    cout<<final<<"\n";
    return 0;
}

 

 

문제 첨부

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

1202번: 보석 도둑