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

작성자	임혜진
소 감	우선순위 큐를 활용하는 것이 익숙치 않아 생각하기 어려웠다. 그리고 어떤 것을 기준으로 탐색해야 할지, 어떤 것을 기준으로 정렬해야 할지 생각하는 것이 너무 어려웠다. 정답 코드를 살핀 후 나중에 다시 문제를 풀어 정답을 맞췄다. 정답을 보고 이해하면 그렇구나 싶은데 처음 문제를 접해서 바로 아이디어를 떠올리기는 매우 어려운 것 같다. 'n번째 가방에 담을 수 있는 보석은 n+1번째에도 담길 수 있다'라는 우선순위 큐의 핵심 아이디어가 신기했다. 당연한 것인데 이를 떠올려 활용하기가 쉽지 않았고 기발했다.
일 시	2025. 3. 10. (월) 18:00 ~ 21:00
장 소	미래관 429호 자율주행스튜디오
참가자 명단	신수민, 임혜진, 배세은, 김윤희 (총 4명)
사 진

 

---

 

📍문제 링크

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을 하려고 하면 에러가 발생할 것이다.