백준 1202 - 보석 도둑

1202번: 보석 도둑 (acmicpc.net)

1202번: 보석 도둑

 

풀이과정

가장 비싼 보석부터 최소 무게를 견디는 가방에 넣는다면 최대 가격을 구할 수 있습니다.

일단 가방에 보석을 넣으면 뒤의 선택에 영향을 미치지 않게됩니다.

 

1. priority queue에 보석들을 담아서 가장 비싼 보석이 가장 위에 위치하도록 합니다.

2. multiset에 가방이 견디는 무게를 넣습니다.

일반 set의 경우 중복되는 값이 허용되지 않기 때문에 multiset을 사용했고,

lower_bound 를 통해 "해당 무게보다 같거나 큰 첫 번째 가방"을 쉽게 찾을 수 있습니다.

 

또한 시간복잡도가 선형을 따라가기 때문에 빠른 시간 내에 해결할 수 있습니다.

 

* 총 합이 int 범위를 벗어날 수 있기 때문에 long long int형을 사용했습니다

 

#include <iostream>
#include <set>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N,K;
priority_queue < pair < int,int > > info;
multiset< int > bag;
long long int sum = 0;

void solution() {
    while(!info.empty()) {
        int value = info.top().first;
        int weight = info.top().second;
        info.pop();

        multiset < int >::iterator iter = bag.lower_bound(weight);
        if(iter == bag.end()) continue;

        bag.erase(iter);
        sum += value;
    }
}

int main()
{
    int a,b;
    scanf("%d %d",&N,&K);
    for(int i=0; i<N; i++) {
        scanf("%d %d",&a,&b);
        info.push({b,a});
    }
    int c;
    for(int i=0; i<K; i++) {
        scanf("%d",&c);
        bag.insert(c);
    }
    solution();
    cout << sum << endl;
}