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

1202번: 보석 도둑

 

문제

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

1202번: 보석 도둑

 

 

풀이

보석의 무게와 가격이 주어지고 가방에 담을 수 있는 최대 무게가 주어진다. 가방은 최대 1개의 보석만 담을 수 있다. 훔칠 수 있는 보석의 가격의 최댓값을 구하는 문제.

 

먼저 기본적인 틀은 최대 무게가 가방에 담을 수 있는 보석 중에 가격이 가장 큰 보석을 담는 것이다. 당연히 담을 수 있는 무게가 큰 가방은 많은 보석이 후보일 것이고 작은 가방은 후보가 적을 것이다. 최대한 많이 훔쳐야 하니 작은 가방부터 채우면 된다. 따라서 가방과 보석(무게 기준)을 모두 오름차순으로 정렬하고 순회한다.

 

우선순위 큐를 사용하면 그리디 쉽게 풀 수 있다. 무게가 가장 작은 가방에 담을 수 있는 모든 보석을 우선순위 큐에 넣고 가격이 가장 큰 보석을 sum에 더해준다. 그리고 남은 보석은 자연스레 다음 가방의 후보군에 들게 된다. 이 과정을 반복하면 최댓값을 구할 수 있다.

 

다만 만약 후보군이 없는 경우, 즉 우선순위 큐가 비어있는 경우 해당 가방은 채울 수 없으므로 넘어가야한다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i].first >> v[i].second; // 보석의 무게, 가격
  vector<int> bag(k);
  for (int i = 0; i < k; i++)
    cin >> bag[i]; // 가방의 무게
  // 오름차순 정렬 (보석은 무게 우선)
  sort(v.begin(), v.end());
  sort(bag.begin(), bag.end());
  priority_queue<int> pq;
  int idx = 0;
  long long sum = 0;
  for (int i = 0; i < k; i++) {
    // i번째 가방에 들어갈 수 있는 모든 보석을 pq에 추가
    while (idx < n && v[idx].first <= bag[i]) {
      pq.push(v[idx].second);
      idx++;
    }
    if (!pq.empty()) {
      sum += pq.top();
      pq.pop();
    }
  }
  cout << sum << '\n';
  return 0;
}