BOJ 1202 - 보석 도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

이 문제는 백준 1781 컵라면 (www.acmicpc.net/problem/1781) 문제와 코드 구조가 거의 비슷하다.

그리디와 우선순위 큐를 이용해서 풀어야 하는 문제 유형이다.

 

이 문제를 보고, 보석 가격이 비싼 순서대로 정렬하고, 가방이 무게 제한이 낮은 순으로 정렬해서 하나하나 비교해도 되지 않나라고 생각할 수 있지만, N 과 K 의 최대값이 30만 이므로 무조건 시간초과가 나게 된다.

 

이 문제를 풀기위해서는 먼저, 보석의 정보가 가치와 무게로 주어지고, 가방이 각각 담을 수 있는 무게가 주어지는데,

둘다(보석과 가방) 무게를 기준으로 오름 차순 정렬해준다. 

 

가방의 무게가 제일 덜 나가는거 부터 시작해서 k 번 순회하는데

이때 i 번째 가방의 무게 안으로 들어오는 보석들은 최대힙에 넣어서 정렬한다. (기본 우선순위 큐)

그리고 나서 가장 큰 보석 가치를 가지는 (pq.top()) 값만 빼내서 정답에 더한다

 

이때 정답이 int 범위를 넘어갈 수 도 있기에 long long 타입으로 선언한다.

 

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
int N, K;
vector<pair<int, int>> gem; // 무게, 가치 
vector<int> backpack;
 
bool comp(pair<int, int>& p1, pair<int, int>& p2) {
    return p1.first < p2.first;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> K;
    
    for (int i = 0; i < N; ++i) {
        int m, v;
        cin >> m >> v;
        gem.push_back({m, v});
    }
    
    for (int i = 0; i < K; ++i) {
        int c;
        cin >> c;
        backpack.push_back(c);
    }
    
    sort(gem.begin(), gem.end(), comp); // 보석 무게 오름차순 
    sort(backpack.begin(), backpack.end()); // 가방 무게 오름차순 
    
    priority_queue<int> pq;
    
    int idx = 0;
    long long answer = 0; // 30만* 백만 이 최대가 될 수 있음
     
    for (int i = 0; i < K; ++i) {
        while(idx < N && backpack[i] >= gem[idx].first) {
            pq.push(gem[idx].second); // 보석 가치를 넣어서 최대힙 정렬 
            idx++;
        }
        
        if (!pq.empty()) {
            answer += (long long)pq.top(); // 최대 가치를 가진 보석만 추출 
            pq.pop();
        } 
    }
    
    cout << answer;
    
    return 0;
}