백준 1202번 C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX 300001
using namespace std;

int N; // 보석 수
int K; // 가방 수

pair<int, int> v_jewelry[MAX]; // 보석의 무게와 가치를 저장하는 배열
int v_bag[MAX]; // 가방의 용량을 저장하는 배열
priority_queue<int, vector<int>, less<int>> pq; // 보석 가치를 저장하는 우선순위 큐

long long solve() {
    // 보석과 가방을 정렬
    sort(v_jewelry, v_jewelry + N);
    sort(v_bag, v_bag + K);

    int idx = 0; // 보석 배열을 탐색하기 위한 인덱스
    long long sum = 0; // 최종 결과값을 저장하는 변수

    // 가방을 순회하면서 보석을 담기
    for (int i = 0; i < K; i++) {
        // 현재 가방의 용량이 보석의 무게보다 크거나 같을 때까지 보석을 우선순위 큐에 추가
        while (idx < N && v_bag[i] >= v_jewelry[idx].first) {
            pq.push(v_jewelry[idx].second); // 보석 가치를 우선순위 큐에 추가
            idx++;
        }
        // 우선순위 큐가 비어있지 않다면 가장 가치가 높은 보석을 꺼내서 결과값에 더함
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }
    return sum;
}

int main() {
    // 입력 받기
    cin >> N >> K;
    
    for (int i = 0; i < N; ++i)
    {
        cin >> v_jewelry[i].first >> v_jewelry[i].second;
    }
    
    for (int i = 0; i < K; ++i) 
    {
        cin >> v_bag[i];
    }

    // 결과 출력
    cout << solve();

    return 0;
}

• 우선순위 큐(Priority Queue)
  • 우선순위에 따라 요소들을 정렬하는 큐 자료구조
  • C++에서는 <queue> 헤더 파일에 priority_queue 클래스로 구현
  • less<int>: 내림차순 정렬
  • 최대 힙(Max Heap)의 형태
    • 최대 힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
    • 가장 큰 값이 항상 루트에 위치
  • priority_queue는 삽입할 때마다 내부적으로 정렬을 유지
  • top() 함수: 가장 우선순위가 높은 요소에 접근
  • pop() 함수: 가장 우선순위가 높은 요소를 큐에서 제거