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

📍문제 링크

https://www.acmicpc.net/problem/1202

 

📍알고리즘 분류

그리디, 우선순위 큐

 

📍 풀이 방법

최대한 많은 보석을 훔치기 위해서는 최대한 비싼 보석을, 많이 담아야 한다.

따라서 비싼 보석부터 담아야 하는데, 최대로 용량을 채울 수 있는 가방에 넣어야 한다.

반복문을 통해 가방을 하나씩 그리디하게 보면서 넣을 보석을 정해준다.

우선순위 큐를 이용해서 하나의 가방 안에 들어갈 수 있는 무게의 보석들 중 가격이 가장 비싼 것을 담으면 된다.

 

어떤 가방부터 보아야할까?

용량이 큰 가방부터 본다면, 비싼데 크기가 작은 보석이 용량이 큰 가방에 담길 것이다. 더 보석을 가져갈 수 있을텐데 용량이 낭비될 것이다.

따라서 용량이 작은 가방부터 탐색한다. 작은 가방에 담기는 무게 중에서 비싼 보석부터 챙기는 것이다.

그러면 최적해가 보장된다.

 

우선순위 큐에 가방 하나에 담을 수 있는 모든 용량의 보석을 담는다.

그 중 가장 가격이 비싼 보석을 선택한다.

다음 가방에 대해서도 이를 반복한다.

핵심은 n번째 가방에도 담을 수 있는 보석은 n+1번째 가방에도 담을 수 있다는 것이다. 용량이 작은 가방부터 탐색하기에 n+1번째 가방은 n번째 가방보다 더 큰 용량의 가방이기 때문이다.

따라서 같은 큐에 계속 넣어주면서 가격을 기준으로 우선순위만 계속 바뀌게 된다. 우선순위 큐에 들어있는 보석들은 모두 현재 보고 있는 가방에 넣을 수 있는, 현재 가방의 용량보다 더 작거나 같은 무게의 보석들이다.

 

이 과정을 정리하면 아래와 같은 로직이 된다.

1) 가방 무게 오름차순 정렬

2) 보석 무게 오름차순 정렬

3) 반복문으로 가방을 하나씩 탐색하며 가방에 넣을 수 있는 보석을 우선순위 큐에 push 후 마지막에 top 보석을 선택

 

 

📍 소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    vector<pair<int,int>> jewels(n);
    vector<int> bags(k);
    for(int i=0;i<n;i++){
        cin>>jewels[i].first>>jewels[i].second;
    }
    for(int i=0;i<k;i++){
        cin>>bags[i];
    }

    sort(bags.begin(), bags.end());
    sort(jewels.begin(), jewels.end());

    long long ans = 0;
    int jewelIndex = 0;

    priority_queue<int> pq;

    for(int i=0;i<k;i++){
        for(int j=jewelIndex;j<n;j++){
            if(bags[i]>=jewels[j].first){
                pq.push(jewels[j].second);
                jewelIndex++;
            }else{
                break;
            }
        }
        if(!pq.empty()){
            ans += pq.top();
            pq.pop();
        }
    }

    cout<<ans<<endl;
}

 

✓ 처음에는 inner for loop에서 j=0부터 n까지 계속 반복하는 것으로 코드를 작성해 틀렸다. 그러면 같은 보석이 여러 개 우선순위 큐에 담길 것이다. 이로 인해 jewelIndex라는 변수가 추가적으로 필요했다. 어디까지 보석을 담았는지 체크해두고 해당 지점부터 for문을 다시 시작하는 것이다.

 

✓ else break;문을 추가하는 것도 중요하다. 보석이 무게 순 오름차순 정렬되어 있기 때문에 한 번 if문에 걸리지 못했다면 그 뒤로도 쭉 if문에 걸리지 않는다. 따라서 바로 break해주는 것이 효율적이다.

 

✓ if(!pq.empty()) 조건도 빼먹었었다. 현재 처리 중인 가방에 넣을 수 있는 보석이 없으면 우선순위 큐가 비어있다. 그런데 이 조건 없이 top을 하려고 하면 에러가 발생할 것이다. 

 

 

 

우선순위 큐를 활용하는 것이 익숙치 않아 생각하기 어려웠다. 그리고 어떤 것을 기준으로 탐색해야 할지, 어떤 것을 기준으로 정렬해야 할지 생각하는 것이 너무 어려웠다. 정답 코드를 살핀 후 나중에 다시 문제를 풀어 정답을 맞췄다. 정답을 보고 이해하면 그렇구나 싶은데 처음 문제를 접해서 바로 아이디어를 떠올리기는 매우 어려운 것 같다. 'n번째 가방에 담을 수 있는 보석은 n+1번째에도 담길 수 있다'라는 우선순위 큐의 핵심 아이디어가 신기했다. 당연한 것인데 이를 떠올려 활용하기가 쉽지 않았고 기발했다.