[백준] 1202번. 보석 도둑

[문제]

 

www.acmicpc.net/problem/1202

1202번: 보석 도둑

[풀이]

 

보석의 무게, 가격과 가방의 무게가 주어지고 가방에 담을 수 있는 보석 가격 합의 최댓 값을 구하는 문제

 

무게를 기준으로 보석과 가방을 오름차순으로 정렬하여 , 가방의 무게를 기준으로 담을 수 있는 보석 무게 중 가격이 가장 높은 것을 선택하는 방식으로 풀었다. 원래는 보석 가격이 가장 높은 것을 선택하기 위해 vector를 사용해  43번째 줄의 while문이 끝날 때마다 vector를 오름차순으로 정렬하여 가장 높은 가격의 보석을 알아냈다. 하지만 시간 초과가 발생하여 priority_queue (우선순위 큐)를 사용해 queue에 push 할 때마다 정렬하도록 하여 시간초과 문제를 해결할 수 있었다.

 

[코드]

 

시간 : 572ms

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define MAX 300001

using namespace std;

struct diamond{
    int weight, value;
};

int bag[MAX]={0,};
int N,K;

bool comp(diamond & a, diamond & b)
{
    return a.weight < b.weight;
}

int main(void)
{
    vector <diamond> v;
    priority_queue <int> q;
    
    cin >> N >> K;
    for(int i=0;i<N;i++){
        int a,b;
        cin >> a>>b;
        v.push_back({a,b});
    }
    for(int i=0;i<K;i++)    cin >> bag[i];
    
    sort(v.begin(),v.end(),comp);
    sort(bag,bag+K);
    
    int idx =0;
    long long int res=0;

    for(int i=0;i<K;i++){
        int weight = bag[i];
        while(idx < N ){
            if(v[idx].weight <= weight){
                q.push(v[idx].value);
                idx++;
            }
            else    break;
        }
        if(q.size()==0 )  continue;
        res+=q.top();
        q.pop();
    }
    cout << res;
    return 0;
}