[백준 1202번] [그리디] 보석 도둑

일단 이 문제를 보고 DP의 대표적인 유형인 Napsack문제를 떠올릴 수 있으나

가방 1개 당 보석 1개만 챙길 수 있다는 점에서 해당 문제와 차이점을 보이고 있다.

 

처음 접근한 방법은 다음과 같다.

만약 무게를 감당할 수 있다면 무조건 무게를 큰 것을 우선적으로 고르는 것이 유리하므로, 무게를 큰 순서대로 배치하고 감당가능한 무게이면 챙기는 방식으로 진행하였다.

 

다만, 이런식으로 진행하게 되면 최악의 경우 각 가방에서 N개를 전체탐색해야하므로

O(NM)이 나와 시간초과가 나오게 된다.

 

근본적으로 시간 초과가 나는 이유가 각 가방에 대해서 보석을 전체 탐색을 하기 때문이다.

발상을 바꿔서 무게를 우선적으로 고려하면, 가방의 한계 무게를 넘지 않는 것 중 가격이 최대인 것을 골라주는 것으로 문제를 바꿔 이해할 수 있다. 즉 구간합의 최대 느낌으로 이 문제를 이해할 수 있고, 이 지점에서 우선순위 큐를 이용한 풀이가 생각나게 되었다.

 

다만, 무게를 다루면서 한번만 보석을 탐색하기 위해서는 오름차순으로 정렬해주어야 한다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int main(void){
    fastio;
    int n, k;
    cin >> n >> k;
    vector<pll> data;
    vector<ll> napsack;

    for(int i = 0; i < n; i++){
        ll temp1, temp2;
        cin >> temp1 >> temp2;
        data.push_back(make_pair(temp1, temp2));
    }

    sort(data.begin(), data.end());

    for(int i = 0; i < k; i++){
        ll temp;
        cin >> temp;
        napsack.push_back(temp);
    }
    sort(napsack.begin(), napsack.end());

    ll result = 0;
    int current_index = 0;
    priority_queue<ll> pq;

    for(int i = 0; i < k; i++){
        for(int j = current_index; j < n; j++){
            if(data[j].first <= napsack[i]){
                pq.push(data[j].second);
                current_index++;
            }
            else{
                break;
            }
        }
        if(!pq.empty()){
            result += pq.top();
            pq.pop();
        }
    }
    cout << result << "\n";
    return 0;
}