[백준-1202] 보석도둑

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

1202번: 보석 도둑

위 문제의 경우 1개의 우선순위큐를 통해 구할 수 있다. 이런 그리디 문제가 나는 비슷한 문제가 많으니 기억해두자.

일단 입력 받은 가방과 보석을 모두 오름차순으로 정렬 한다.

그 후 작은 가방 하나씩 꺼내고, 보석 배열을 순회하면서 집어넣을 수 있는 보석을 우선순위 큐에 집어 넣는다. (by while) 다 집어 넣었으면 우선순위 큐의 top 에 위치하는 보석을 해당 가방에 넣는 것으로 확정하고 그 다음 가방을 똑같은 방법으로 확인하는 로직이다. 말이 쉽지 직접 구현하는 건 좀 어렵다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
int n, k;

int main()
{
    ios_base::sync_with_stdio(0);

    cin.tie(0); //cin 실행속도 향상

    scanf("%d %d", &n, &k);
    vector<pii> jewl;
    vector<LL> bag;
    priority_queue<LL> pq;

    LL m, v, t;
    for (int i = 0; i < n; i++)
    {
        cin >> m >> v;
        jewl.push_back({m, v});
    }

    for (int i = 0; i < k; i++)
    {
        cin >> t;
        bag.push_back(t);
    }
    sort(bag.begin(), bag.end());
    sort(jewl.begin(), jewl.end());

    long long answer = 0;
    int idx = 0;
    for (int i = 0; i < k; i++)
    {
        while (idx < n && jewl[idx].first <= bag[i])
        {
            // 가방에 넣을 수 있는지, 없는지 확인
            pq.push(jewl[idx++].second);
        }
        if (!pq.empty())
        {
        	// 우선순위 큐의 top에 있는 놈이 정답
            answer += pq.top();
            pq.pop();
        }
    }

    cout << answer;

    return 0;
}