[C++] 백준/Gold/1202. 보석 도둑

문제: 보석 도둑 (백준 1202번)

문제 분석

이 문제는 풀이법이 바로 떠오른다면 쉽게 해결할 수 있지만, 그렇지 않다면 접근법을 찾기 어려운 웰메이드 문제이다.
알고리즘 자체는 복잡하지 않으나, 핵심 아이디어를 도출하는 것이 도전 과제다.

핵심 아이디어

1. 정렬
   • 가방과 보석을 무게 순으로 오름차순 정렬한다.
   • 작은 가방부터 차례로 탐색하며 해당 가방에 들어갈 수 있는 보석들을 선택한다.
2. 우선순위 큐
   • 현재 가방에 들어갈 수 있는 보석들을 모두 우선순위 큐에 삽입한다.
   • 이때, 우선순위 큐는 보석의 가치를 기준으로 내림차순 정렬되도록 설정한다.
   • 우선순위 큐의 맨 앞에 있는 보석은 현재 가방이 담을 수 있는 최고 가치의 보석이다.
3. 탐욕적 선택
   • 작은 가방부터 순서대로 처리하며, 현재 가방이 담을 수 있는 최고 가치의 보석을 선택한다.
   • 이를 통해 전체 가치의 합을 최대화한다.

---

구현

주요 변수 및 알고리즘

• gem: 보석의 (무게, 가치) 쌍을 저장하는 벡터.
• bag: 각 가방의 무게 제한을 저장하는 벡터.
• pq: 우선순위 큐로, 현재 가방에 담을 수 있는 보석의 가치만 저장.
• answer: 모든 가방이 담을 수 있는 보석들의 총 가치를 저장.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;

    // 보석과 가방 입력
    vector<pair<int, int>> gem(n);
    vector<int> bag(k);
    for (int i = 0; i < n; i++) cin >> gem[i].first >> gem[i].second;
    for (int i = 0; i < k; i++) cin >> bag[i];

    // 무게 순으로 정렬
    sort(gem.begin(), gem.end());
    sort(bag.begin(), bag.end());

    // 우선순위 큐 및 결과값 초기화
    long long answer = 0;
    priority_queue<int> pq;

    // 가방을 순회하며 보석 선택
    for (int i = 0, j = 0; i < k; i++) {
        // 현재 가방에 들어갈 수 있는 모든 보석을 우선순위 큐에 삽입
        while (j < n && gem[j].first <= bag[i]) {
            pq.push(gem[j].second);
            j++;
        }
        // 우선순위 큐에서 가장 가치가 높은 보석을 선택
        if (!pq.empty()) {
            answer += pq.top();
            pq.pop();
        }
    }

    cout << answer;
}