[백준 1202] 보석 도둑 (C#, C++) - soo:bak

문제 링크

1202번 - 보석 도둑

설명

N개의 보석 (각각 무게와 가치)과 K개의 가방 (각각 용량)이 주어지는 상황에서, N ≤ 300,000, K ≤ 300,000이 주어질 때, 각 가방에 최대 1개의 보석을 담되 가방 용량 이하의 무게인 보석만 담을 수 있다는 조건 하에 훔칠 수 있는 보석 가치 합의 최댓값을 구하는 문제입니다.

접근법

그리디 알고리즘과 우선순위 큐를 사용하여 최적의 선택을 합니다.

먼저 보석을 무게 기준 오름차순으로, 가방도 용량 기준 오름차순으로 정렬합니다.

가방을 작은 용량부터 순회하면서, 현재 가방에 담을 수 있는 모든 보석을 최대 힙에 넣습니다. 이때 가치를 기준으로 최대 힙을 구성합니다.

이후 힙에서 가장 가치가 큰 보석을 꺼내 현재 가방에 담습니다. 이렇게 하면 매 가방마다 담을 수 있는 보석 중 가장 가치 있는 것을 선택하게 되어 전체 가치 합이 최대가 됩니다.

시간 복잡도는 O((N+K) log N)입니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var n = first[0];
      var k = first[1];

      var jewels = new (int w, int v)[n];
      for (var i = 0; i < n; i++) {
        var parts = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        jewels[i] = (parts[0], parts[1]);
      }
      Array.Sort(jewels, (a, b) => a.w.CompareTo(b.w));

      var bags = new int[k];
      for (var i = 0; i < k; i++)
        bags[i] = int.Parse(Console.ReadLine()!);
      Array.Sort(bags);

      var pq = new PriorityQueue<int, int>();
      var ans = 0L;
      var idx = 0;
      foreach (var cap in bags) {
        while (idx < n && jewels[idx].w <= cap) {
          pq.Enqueue(jewels[idx].v, -jewels[idx].v);
          idx++;
        }
        if (pq.Count > 0) {
          pq.TryDequeue(out var val, out _);
          ans += val;
        }
      }

      Console.WriteLine(ans);
    }
  }
}

C++

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

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

  int n, k; cin >> n >> k;
  vpii jewel(n);
  for (int i = 0; i < n; i++)
    cin >> jewel[i].first >> jewel[i].second;
  vi bag(k);
  for (int i = 0; i < k; i++)
    cin >> bag[i];

  sort(jewel.begin(), jewel.end());
  sort(bag.begin(), bag.end());

  priority_queue<int> pq;
  ll ans = 0;
  int idx = 0;
  for (int cap : bag) {
    while (idx < n && jewel[idx].first <= cap) {
      pq.push(jewel[idx].second);
      idx++;
    }
    if (!pq.empty()) {
      ans += pq.top();
      pq.pop();
    }
  }

  cout << ans << "\n";
  return 0;
}