[Baekjoon,1202] 보석 도둑

초기에는 무식하게 접근하였다. 가방의 용량을 오름차순으로 정렬하고 보석의 무게를 기준으로 오름차순으로 정렬했다. 그 이후 가방에 들어갈 수 있는 모든 보석들을 비교하며 가장 가치가 큰 보석을 가방에 넣었다. 이를 가방의 용량이 작은 것 부터 처리했다. 하지만 이 방법은 $300,000$개의 가방과 보석들을 처리하기에는 반복되는 부분이 너무 많아 느려 문제를 해결할 수 없다.

반복되는 부분을 없애자

이를 해결하는 방법은 이미 확인 했던 보석들을 중복하여 비교하는 것을 막는 것이다. 이전 가방의 무게가 $5$였다면 무게가 $5$ 이하인 보석은 이미 비교를 다 했을 것이다. 이번의 가방의 무게가 $10$이라면 이전에 비교한 무게가 $5$ 이하인 보석에서 무게가 $10$인 보석들을 추가로 비교하기만 하면 된다는 것이다.

이를 구현할 수 있는 가장 좋은 자료구조는 바로 우선순위 큐 이다. 현재 가방에 들어갈 수 있는 보석들을 모두 큐에 넣고 가장 $top$에 있는 원소를 꺼내어 결과에 더한다. 다음 가방에는 모든 보석을 탐색하지 않고 이전에 탐색을 끝낸 다음 원소부터 탐색하여 큐에 넣으면 된다. 이것이 가능한 이유는 가방과 보석을 오름차순으로 정렬했기 때문이다.

구현

이에 대한 구현을 아래에서 볼 수 있다. 주의할 점은 결과 값이 $int$형 범위를 벗어날 수 있기 때문에 $long long$으로 선언해야 하는 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX=300001;

int n,k;
// <mass,value>
vector<pair<int,int> > jew; 
int capacity[MAX];

long long solve()
{
    priority_queue<int> pq;
    long long ret=0;
    int idx=0;
    for(int i=0;i<k;++i)
    {
        int limit=capacity[i];
        // 현재 가방에 들어 갈 수 있는 보석을 큐에 넣는다.
        while(idx<n && jew[idx].first<=limit)
            pq.push(jew[idx++].second);
        
        // 넣을 수 있는 보석이 있을 때
        if(!pq.empty())
        {
            // 가장 큰 보석을 가방에 넣는다.
            ret+=pq.top();
            pq.pop();
        }
    }
    return ret;
}

int main()
{
    cin>>n>>k;
    jew=vector<pair<int,int> >(n);
    for(int i=0;i<n;++i)
    {
        int m,v;
        scanf("%d %d",&m,&v);
        jew[i]=make_pair(m,v);
    }
    for(int i=0;i<k;++i)
        scanf("%d",&capacity[i]);
    
    sort(jew.begin(), jew.end());
    sort(capacity,capacity+k);
    
    cout<<solve()<<endl;

    return 0;
}