[백준][C++] 1202 보석 도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

 

 

알고리즘 종류

    - 그리디(greedy)

    - 힙 구조(heap)

 

 

 

사고 과정

    - 무게가 작은 가방부터 가장 비싼 보석을 넣는다.

    [그리디 문제는 확신이 없습니다. 틀린 부분이 있으면 댓글로 알려주시면 감사하겠습니다.]

        1. 가방과 보석을 무게 순으로 오름차순 정렬한다.

        2. 가방의 무게 이하인 보석을 모두 최대 힙에 저장합니다.

        3. 최대 힙에서 가장 큰 값을 answer에 저장합니다.

 

    - 왜?

        : 가장 큰 가방에 아래와 같이 담길 수 있는 보석들이 있습니다. 여기서 가장 비싼 보석을 고릅니다. 다음으로 큰 가방에서 비싼 보석을 고릅니다. 계속하다면, 가장 작은 가방에서 가장 비싼 보석을 고릅니다. 이렇게 되면, 가방에 들어갈 수 있는 보석들 중에 가장 비싼 보석을 고르면 됩니다.

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int n, k;
int m, v;
long long answer = 0;
 
vector<pair<int, int> > jews; // weight, value 
vector<int> bags;
 
 
bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first < b.first;
}
 
 
int main(void){
    
    cin >> n >> k;
    
    for(int i=0; i<n; i++){
        cin >> m >> v;
        jews.push_back({m, v});
    }
    
    for(int i=0; i<k; i++){
        cin >> m;
        bags.push_back(m);
    }
    
    sort(bags.begin(), bags.end());
    sort(jews.begin(), jews.end(), cmp);
    
    // 가방 무게 w까지 보석들 넣을 container 
    priority_queue<int> pq;
    int j = 0;
    
    for(int i=0; i<bags.size(); i++){
        int w = bags[i];
        
        for(; j<jews.size(); j++){
            if(jews[j].first > w) break;
            pq.push(jews[j].second);    
        }
        
        // 가방무게가 10이라고 할 때, 보석들 중 최소 무게가 12면, 넣을 보석이 없음
        // 이럴 경우, 오류가 발생하므로 이를 제외하기 위한 조건을 넣는다.  
        if(pq.size()){
            answer += pq.top();
            pq.pop();
        }
    }
    
    cout << answer << endl;
}
 
 
 
 

 

 

 

시행착오

    - 무게가 가장 작은 가방에 가장 비싼 보석을 넣으면 될 것 같다는 생각이 들었다. 그런데, 왜 그런 것일까 스스로 궁금했다. 검색을 해보아도 아직 이해하기는 힘들었다. 다음에 다시 한 번 도전해 봐야겠다.