[백준/C++] 보석 도둑 (No. 1202)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때, 정렬을 이용해 가장 가치가 높은 보석부터 가방에 넣을 수 있는지 확인하고, 무게가 가장 비슷한 가방에 넣으면 되겠다는 생각을 했다.

 

하지만, 문제는 사용한 가방에 있었다.

이분 탐색으로 적절한 가방을 찾는 과정에서 이미 사용한 가방을 삭제하지 않고 처리할 적당한 방법이 떠오르지 않았다.

(만약 삭제할 경우 삭제하는 과정에서 O(N)의 시간복잡도가 필요하기 때문에 문제의 시간복잡도는 O(N^2)이 된다.)

 

그래서 반대로 가방의 무게를 기준으로 보석을 찾도록 방법을 바꿨다.

 

하나의 가방에는 하나의 보석만 들어가기 때문에 그 가방에 넣을 수 있는 보석 중 가장 가치가 높은 보석을 넣으면 된다.

 

이 과정에서 priority_queue를 이용했다.

 

먼저 보석과 가방을 무게를 기준으로 오름차순 정렬한다.

(만약 가방의 무게가 무거운 순서로 탐색을 하면 priority_queue에서 제거하는 과정에서 조금 더 시간이 걸리게 된다)

 

이후 가방에 넣을 수 있는 보석들은 전부 priority_queue에 집어넣는다.

여기서 priority_queue는 보석의 가치를 기준으로 정렬되어있다.

 

그 다음 priority_queue에서 가장 가격이 높은 보석을 골라 가방에 넣고 priority_queue에서 제거한다.

 

마찬가지로 다음 가방도 가방에 넣을 수 있는 보석을 전부 priority_queue에 넣은 후 가장 가치가 높은 보석을 가방에 넣으면 된다.

 

(여기서 가방의 무게가 가벼운 순서대로 탐색을 시작했기 때문에 이전 가방에서 priority_queue에 넣은 보석은 전부 현재 가방에 넣을 수 있는 보석이 된다)

 

모든 가방에 대해 탐색이 끝나면, 가방에 넣은 보석들의 가치를 출력하면 된다.

 

 

​

[아이디어 정리]

1. 가방과 보석을 무게를 기준으로 오름차순 정렬을 한다.
2. 그리고 가방을 가벼운 순서대로 선택하며 가방에 넣을 수 있는 보석은 전부 priority_queue에 넣는다.
3. priority_queue는 보석의 가치가 높은 순서대로 정렬되어 있으므로, 가장 가치가 높은 보석을 가방에 넣는다.
4. 모든 가방에 대해 위 과정을 반복한다.
5. 가방에 넣은 모든 보석의 가치를 출력한다.

 

 

 

Code

 

 

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

struct cmp {
    bool operator ()(int a, int b) {
        return a < b; // 비싼 순서
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> VC(N);
    long long a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        VC[i]=make_pair(a,b); // 무게 가격
    }
    sort(VC.begin(), VC.end(), [](pair<int, int> a, pair<int,int>b) {
        return a.first<b.first; }); //무게가 가벼운 순서대로 정렬
    vector<long long> bag(K);
    for (int i = 0; i < K; i++) {
        cin >> bag[i];
    }

    sort(bag.begin(), bag.end(), [](int a, int b) {return a < b; }); // 가방 무게가 가벼운 순서
    int idx=0;
    long long ans = 0;
    priority_queue <int, vector<int>, cmp> pq;
    for (int i = 0; i < K; i++) 
    {
        while (idx < N) { // 가방보다 가벼운 보석 전부 pq에 넣기
            if (bag[i] >= VC[idx].first) {
                pq.push(VC[idx].second);
            }
            else {
                break;
            }
            idx++;
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans << endl;


    return 0;
}

 

---

처음에 보석을 기준으로 가방을 선택하려다 보니 어려웠다.

보석의 가치가 가장 높은 경우에 최적의 가방을 찾는 것은 이분탐색으로 구현하면 되지만, 그 이후에 가방을 제거하는 과정이 필요했기 때문이다.

그래서 다른 방법을 생각하다가 보석의 가치 대신 가방의 무게를 기준으로 생각했더니 쉽게 풀 수 있었다.

 

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