Gidhub BE Developer

[BOJ] 보석 도둑

2018-02-20
goodGid
Algorithm

Problem

Problem URL : 보석 도둑

Explain Logic

큰 가방은 작은 가방이 넣을 수 있는 보석을

모두 넣을 수 있다.

그렇기 때문에

작은 가방에 들어갈 수 있는

가능한 보석의 Value를 Priority Queue에 넣고

그 중 Root에 있는걸 pop 한다.

(= Max Value pop)


여기서 핵심이

그 다음 가방은 현재 가방이 담을 수 있는 보석들을 담을 수 있기 때문에

현재 가방에 대한 위의 과정 + 현재 Priority Queue의 값들 중에서

Root를 pop한다.

이 말이 이해가 안간다며 Code를 참고하자.


Priority Queue가 유지되기 때문에

무게로 sort를 하지만

무게는 더 무겁지만 가치가 작은값은

어차피 Priority Queue는 Value를 기준으로 정렬을 하기 때문에

최적의 해가 구해진다.

이 말이 이해가 안간다면 Code를 참고하자.

[1] Answer Code (18. 02. 20)


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

typedef pair<int, int> p;
vector<p> v;
vector<int> b; // b is bag

int main(){
    int n,k;
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        int a,b;
        scanf("%d %d",&a, &b);
        v.push_back({a,b});
    }
    
    for(int i=1; i<=k; i++){
        int a;
        scanf("%d",&a);
        b.push_back(a);
    }
    
    sort(v.begin(),v.end());
    sort(b.begin(), b.end());
    
    priority_queue<int> q;
    long long sum = 0;
    // i : Bag index -- k
    // j : Jewelry index -- n
    for(int i=0,j=0; i<k; i++){
        while ( j<n && v[j].first <= b[i]) {
            q.push(v[j++].second);
        }
        
        if(! q.empty()){
            sum += q.top();
            q.pop();
        }
    }
    
    cout << sum << endl;
    
    return 0;
}

Code Review

[1] Answer Code (18. 02. 20)

  • 알고리즘이 생각나지 않아 답을 참고하였다.

  • 아이디어 심플하고 굉장히 좋다.

  • typedef pair<int, int> p; 이런식 선언으로 해봤다.

Index