[ 백준 / C++ ] 1202 : 보석 도둑

[ 문제 ]

 

1202번: 보석 도둑

 

[ 접근방법 ]

 

먼저 입력으로 받은 보석과 가방을 오름차순으로 정렬한다.

 

그 후, 가방을 순서대로 보면서(무게가 낮은 것부터) 넣을 수 있는 보석의 가격을 우선순위 큐에 집어넣는다.

 

가방에 넣을 수 있는 가격이 가장 높은 보석을 우선순위 큐를 통해 빠르게 선별 가능하다.

 

가방에 보석을 넣었다면 pop을 통해 제거하고 이 과정을 반복하면 된다.

 

[ 소스코드 ]

 

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

using namespace std;

struct Jew
{
    int m, v;
};
bool cmp(Jew x, Jew y)
{
    if (x.m < y.m)
        return true;
    else if (x.m == y.m)
        return x.v < y.v;
    return false;
}

int n, k, idx;
long long ans;
priority_queue<int> pq;
vector<Jew> j;
vector<int> b;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    j.resize(n);
    for (int i = 0; i < n; i++)
        cin >> j[i].m >> j[i].v;

    b.resize(k);
    for (int i = 0; i < k; i++)
        cin >> b[i];

    sort(j.begin(), j.end(), cmp);
    sort(b.begin(), b.end());

    for (auto i : b)
    {
        while (idx < n && j[idx].m <= i)
            pq.push(j[idx++].v);
        if (!pq.empty())
        {
            ans += pq.top();
            pq.pop();
        }
    }

    cout << ans;

    return 0;
}