백준 1202번 [보석 도둑](C++) -yes6686- 티스토리

백준 문제 풀이: 1202 [보석 도둑]

---

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

문제 설명:

강도는 N개의 보석과 K개의 가방을 가지고 있습니다. 각 보석은 무게와 가치가 있으며, 가방은 담을 수 있는 최대 무게가 정해져 있습니다. 보석의 무게가 가방의 허용 무게보다 작거나 같아야 가방에 넣을 수 있습니다.

강도는 최대의 가치를 얻기 위해 보석을 선택하려고 합니다. 보석의 최대 가치를 계산하는 문제입니다.

---

문제 해결 코드

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

priority_queue<int, vector<int>, greater<int>> bag;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> jewel;
priority_queue<pair<int, int>> q;

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

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        int m, v;
        cin >> m >> v;
        jewel.push({m, v});
    }

    for (int i = 0; i < k; i++) {
        int c;
        cin >> c;
        bag.push(c);
    }

    long long ans = 0;
    while (!bag.empty()) {
        int maxWeight = bag.top();
        bag.pop();

        while (!jewel.empty()) {
            int weight = jewel.top().first;
            int value = jewel.top().second;
            if (maxWeight >= weight) {
                q.push({value, weight});
                jewel.pop();
            } else {
                break;
            }
        }

        if (!q.empty()) {
            ans += q.top().first;
            q.pop();
        }
    }

    cout << ans << '\n';
}

예제

입력:
3 2
1 65
5 23
2 99
10
2

출력:
164

---

코드 설명

• 입력 처리: 보석의 무게와 가치를 우선순위 큐(jewel)에 저장하며, 무게 기준으로 정렬합니다. 가방의 무게 허용치는 별도의 우선순위 큐(bag)에 저장합니다.
• 보석 선택: 각 가방 무게를 기준으로, 해당 무게를 초과하지 않는 모든 보석을 가치 기준으로 우선순위 큐(q)에 추가합니다.
• 최대 가치 선택: 가방에 담을 수 있는 보석 중 가장 높은 가치를 선택하여 총합에 추가합니다.
• 출력: 강도가 가져갈 수 있는 보석 가치의 최대 합을 출력합니다.

시간 복잡도

• 보석 처리: O(N log N)
• 가방 처리: O(K log N) (각 가방에 대해 보석 처리)
• 전체 복잡도: O(N log N + K log N)

---

결과

코드는 보석과 가방의 조건에 따라 최적의 보석 선택을 통해 문제를 해결합니다. 추가적인 테스트를 통해 성능을 확인할 수 있습니다.