보석 도둑

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
int N, K;
vector<pair<int,int>> v;
vector<int> bag;
priority_queue<int> pq;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    /* 핵심 : 가방에 넣을 수 있어야 가격이 비싸든말든 의미가 있음
             --> 가방에 넣을 수 있는게 우선, 그 중 가격이 가장 비싼 것을 빼면 됨 */
    cin >> N >> K;
    for(int i=0;i<N;i++)
    {
        int a,b;
        cin >> a >> b;
        v.push_back({a,b});
    }
    for(int i=0;i<K;i++)
    {
        int a;
        cin >> a;
        bag.push_back(a);
    }
    sort(bag.begin(), bag.end()); // 가방 무게가 작은게 앞으로
    sort(v.begin(), v.end()); // 보석의 무게가 작은게 앞으로
    int idx=0;
    ll result = 0;
    for(int i=0;i<bag.size();i++) 
    {
        // 가방에 들어가는 보석은 일단 큐에 넣고 본다
        while(idx < v.size() and v[idx].first <= bag[i])
            pq.push(v[idx++].second);
        // 가방에 있는 보석 중 제일 값이 비싼 것 하나를 pop()
        if(!pq.empty())
        {
            result += pq.top();
            pq.pop();
        }
    }
    cout << result;
    return 0;
}

• 핵심
  • 가방에 넣을 수 있어야 가격이 비싸든 말든 의미가 있다
    --> 즉, 가방에 넣을 수 있는 모든 보석을 고른 후 가장 비싼 보석을 선택하면 됨
  • 그리디 + 우선순위 큐 사용