1202 보석 도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

처음에 이 문제를 보고 바로 동전DP를 떠올렸지만, 각 가방에 한 개의 보석만 넣을 수 있고, 각각의 가방에 넣을 수 있는 보석의 무게가 다르기 때문에 조금 다른 문제라 생각했다.

 

풀이 방법

 

용량이 작은 가방부터 넣을 수 있는 최대 가치의 보석을 넣으면 된다.

예를들어, 아래와 같은 상황이라고 하자.

먼저 가방 용량을 오름차순으로 정렬하고, 보석을 무게를 기준으로 오름차순으로 정렬한다.

용량이 가장 작은 5부터 보석을 넣는다고 하면,

빨간색인 4가지 보석들을 넣을 수 있다.

이 때, 가장 가치가 큰 보석을 하나 넣으면 된다.

 

여기서 이미 무게를 기준으로 정렬되어있는 보석을, 다시 가치를 기준으로 정렬을 해야하는 상황이 발생한다.

그러면서 다음 가방에 넣을 보석들은 다시 무게를 기준으로 정렬되어있어야 어떤 보석은 넣을 수 있고, 없는지를 빠르게 판단할 수 있다.

 

이런 상황에서 문제를 해결할 수 있는 기법은 정형화 되어있으니, 다른 문제를 풀 때 이 방법을 기억하자.

 

바로 우선순위 큐를 이용한 방법이다.

 

용량이 작은 가방부터 시작해서 해당 가방 용량에 넣을 수 있는 보석들을 모두 우선순위 큐 안에 넣는다.

(이 때, 보석을 어디까지 넣었는 지 인덱스를 저장해서 다음에 사용해야한다.)

우선순위 큐 안에 들어있는 모든 보석들은 해당 가방에 넣을 수 있으므로, 우선순위 큐에서 가장 큰 가치를 가진 보석을 꺼내 answer 값에 더한다.

 

다음 가방에서도 동일하게 적용하는데, 다음 가방은 이전 가방보다 용량이 크므로 지금 우선순위 큐 안에 들어있는 모든 보석들은 해당 가방에 넣을 수 있다.

이것을 기반으로 우선순위 큐 안에 더 넣을 보석이 있으면 넣고, 우선순위 큐에서 하나 더 꺼내 answer 값에 더한다.

 

위 과정을 반복하면 해답을 찾을 수 있다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    vector<pair<lld, lld>> mv(n);
    vector<lld> c(k);
    for(int i=0;i<n;i++)
        cin >> mv[i].first >> mv[i].second;
    for(int i=0;i<k;i++)
        cin >> c[i];
    sort(mv.begin(), mv.end());
    sort(c.begin(), c.end());
    lld ans = 0LL;
    int idx = 0;
    priority_queue<lld, vector<lld>, less<lld>> pq;
    for(int i=0;i<k;i++)
    {
        while(idx<n && mv[idx].first<=c[i])
        {
            pq.push(mv[idx++].second);
        }
        if(pq.size())
        {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans;
 
    return 0;
}