백준 1202

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다

풀이

각 가방에다 최대한 비싼 보석을 넣으면 풀리는 문제이다.

문제 자체는 이렇게 간단하지만 N, K가 300000까지라 O(NlogN) 이하의 시간복잡도를 가지게 구상해야 한다는 것을 알 수 있다.

이렇게 구현하기 위해서는 priority_queue(heap) 에 대한 정보를 알고 있어야 한다.

heap은 complete binary tree의 구조로
높이는 최대 logN밖에 되지 않으며 각 노드가 들어와서 갱신되는데 logN의 시간밖에 걸리지 않는다.

우선 보석과 가방을 모두 입력받아 무게의 내림차순으로 정렬해준다. (max-heap)

priority_queue<pair<int,int>,vector<pair<int,int>>>jewel;
priority_queue<int,vector<int>>bag;
for(int i=0; i<N; i++){
        int m,v;
        cin>>m>>v;
        jewel.push({m,v});
    }
    for(int i=0; i<K; i++){
        int a;
        cin>>a;
        bag.push(a);
    }

그 다음 보석의 top의 무게가 가방에 수용할 수 있는 무게보다 크다면, 이 보석은 들어갈 수 없으니 없애주고, 만약 들어간다면 보석과 가방을 하나씩 제거해주고, 가격정보를 따로 저장해준다.

priority_queue<int,vector<int>,greater<>>value;

그렇게 해서 만약 가방이 비었으면 가격을 저장해놓은 자료구조(value_pq, min-heap)에서 가장 작은값과, 넣고싶은 보석의 가격을 비교하여 만약 보석의 가격보다 value_pq.top()이 더 작다면 value_pq.pop() -> value_pq.push(cur_jewel)을 해주고 더 크다면 그냥 현재 보석을 버리면 된다.

만약 현재 보석의 무게가 남아있는 가방의 무게보다 크다면 지금까지 저장된 가격과 다시 비교해주면 된다.

개념 자체는 어렵지 않은데 말로 설명하려니 중구난방이 된거같다..

시간복잡도(정확하지 않음)

N개의 보석을 pq에 넣어 max-heap을 만드는 시간은 O(NlogN)이다.
N개의 노드가 전부 들어가고, 하나의 노드가 들어갈때 갱신되는 시간이 logN이기 때문이다.

보석을 하나하나 돌아보면서 갱신하는 코드도
보석의 개수 N, value_pq를 갱신하는 시간 logN밖에 걸리지 않아

이 문제는 O(NlogN)에 풀 수 있게 된다.

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
long long N,K,ans_s;
priority_queue<pair<int,int>,vector<pair<int,int>>>jewel;
priority_queue<int,vector<int>>bag;
priority_queue<int,vector<int>,greater<>>value;
int main(){
    cin>>N>>K;
    for(int i=0; i<N; i++){
        int m,v;
        cin>>m>>v;
        jewel.push({m,v});
    }
    for(int i=0; i<K; i++){
        int a;
        cin>>a;
        bag.push(a);
    }
    while(!jewel.empty()){
        auto cur = jewel.top();
        jewel.pop();
        if(!bag.empty() && bag.top() < cur.first){
            if(value.empty())
                continue;
            if(cur.second > value.top()){
                value.pop();
                value.push(cur.second);
            }
            continue;
        }
        if(bag.empty()){
            if(value.top() < cur.second){
                value.pop();
                value.push(cur.second);
            }
        }else{
            bag.pop();
            value.push(cur.second);
        }
    }
    while(!value.empty()){
        ans_s += value.top();
        value.pop();
    }
    cout<<ans_s;

}