Beakjoon 1202 보석 도둑

02 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1202

나의 풀이

처음 접근했던 방식은 보석을 가격 기준으로 정렬하고 가방을 무게 기준으로 정렬한 뒤 가장 작은 가방부터 최대한 비싼 보석을 탐색하도록 하려 했다. 하지만 이 경우 O(NK)의 시간복잡도를 갖게 되고, N과 K가 각각 최댓값이 300,000이기 때문에 시간 초과에 걸리게 된다.
시간 초과 문제를 해결하고 문제를 해결하는 방법은 보석을 무게를 기준으로 정렬하고, 가장 작은 가방부터 가방에 담을 수 있는 모든 보석의 가격을 priority_queue에 넣고 priority_queue의 top에 있는 가장 비싼 가격을 정답에 추가해준다. 결과적으로 이 과정에서의 시간 복잡도는 O(N+K)가 되고, 결과적으로는 보석과 가방을 정렬할 때의 시간복잡도인 O(NlongN) or O(KlogK)로 시간 초과를 피해서 문제를 해결 할 수 있다.

풀이 코드 : 1202 보석 도둑

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

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first)
        return a.second > b.second; 
    return a.first < b.first;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<pair<int, int>> jewelry; // 무게, 가격
    vector<int> bag;
    
    int N,K, m, v, c;
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>m>>v;
        jewelry.push_back(make_pair(m, v));
    }
    for(int i=0;i<K;i++){
        cin>>c;
        bag.push_back(c);
    }

    sort(jewelry.begin(), jewelry.end(), compare);
    sort(bag.begin(), bag.end());
    
    long long answer = 0;
    int count = 0, j=0;
    priority_queue<int> pq;
    for(int i=0; i<K ;i++){
        while(j<N && bag[i] >= jewelry[j].first) 
        {   
            pq.push(jewelry[j].second);
            j++;
        }
        if(!pq.empty()){
            answer += pq.top();
            pq.pop();
        }
    }
    cout<<answer;

}

채점결과