[백준] [C++] 1202번 보석 도둑 (greedy, priority queue)

1. 문제

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

1202번: 보석 도둑

 

2. 풀이 

이 문제는 탐욕법으로 해결할 수 있다.

가장 값비싼 보석을 가능한 가방중 가장 용량이 작은것에 넣는 것이다.

 

하지만 배열을 사용하여 문제를 풀 시 시간초과가 나온다.

따라서 적절히 사용한 가방을 제외 하고, 빠르게 작은 가방을 찾을 수 있는 자료구조를 사용해야한다.

map을 사용하면 빠르게 원소를 제외할 수 있고,  최소 원소 또한 찾을 수 있다.

 

 

전체적인 알고리즘은 다음과 같다

1) 보석을 가중치 V에 대하여 정렬

2) 가방을 map에 담아 자동적으로 정렬, 중복된 개수를 value로

3) 가중치가 제일 높은것을 담을 수 있는 가방중 가장 작은 용량에 담는다.

4) 가방에 넣으면 그 가방은 고려대상에서 제외한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
 
using namespace std;
int N, K;
map<int, int> C;
vector<pair<int, int> > item;
long long answer = 0;
 
 
void solve(int iidx) {
    if(iidx == -1) {
        return;
    }
    auto lo = C.lower_bound(item[iidx].second);
 
    for(auto it = lo; it != C.end(); it++) {
        if(it->second > 0) {
            answer += item[iidx].first;
            it->second--;
            if(it->second == 0) {
                C.erase(it->first);
            }
            break;
        }
    }
    return solve(iidx-1);
}
 
int main() {
    cin>> N >> K;
    item = vector<pair<int, int> >(N);
 
    for(int i = 0; i < N; i++) {
        cin>>item[i].second>>item[i].first;
    }
    sort(item.begin(), item.end());
    for(int i = 0; i < K; i++){
        int tmp;
        cin>>tmp;
        C[tmp]++;
    }
    solve(N-1);
    cout<<answer;
}

3. 다른사람 풀이 - priority queue

 

백준 1202번 보석 도둑 (tistory.com)