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

접근방법

Greedy 알고리즘을 사용한다. 만약 브루트포스로 풀게 되면 시간초과가 나게된다.

풀이방법

무게가 적은 가방부터 큰 가방들까지 각 가방에 들어갈수있는 보석들 중 가치가 높은 보석을 넣으면 된다.
각 단계마다 최적의 선택을 하므로, 그리디 알고리즘이다.
위와 같이 무게가 적은 가방부터 채워넣는다. 단, 넣을 수 있는 보석중 가장 가치가 높은 보석을 넣는것이다.

이 그리디 알고리즘은 탐욕적 선택 속성과 최적 부분 구조를 만족하기 때문에 그 정당성을 증명할 수 있다.(정당성 증명은 추후 추가)

우선순위 큐 사용

무게 제한이 낮은 가방부터 높은 가방으로 순회하면서 그 가방이 가질 수 있는 보석들의 가치를 priority queue에 넣어준다.
이 때, 보석은 무게 순으로 오름차순 정렬되어있기 때문에, 보석 배열에 인덱스를 늘려가면서 찾아준다.
다음 가방이 가질 수 있는 보석들을 찾을 때에 보석 배열의 인덱스는 처음부터 찾는 것이 아닌, 그 다음 보석부터 찾으면 된다.
즉, 보석은 한번씩만 priority queue에 들어간다.

소스코드

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

using namespace std;

vector<pair<int, int> > gem;
vector<int> bag;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int N,K,index=0;
    long long sum = 0;
    priority_queue<int> pq;
    cin >> N >> K;
    for(int i=0; i<N; i++){
        int M,V;
        cin >> M >> V;
        gem.push_back(make_pair(M, V));
    }
    for(int i=0; i<K; i++){
        int C;
        cin >> C;
        bag.push_back(C);
    }
    sort(gem.begin(), gem.end());
    sort(bag.begin(), bag.end());
    for(int i=0; i<K; i++){
        while(gem[index].first <= bag[i] && index < N){
            pq.push(gem[index++].second);
        }
        if(!pq.empty()){
            sum += pq.top();
            pq.pop();
        }
    }
    cout << sum << "\n";
}