[BOJ] 1202 - 보석 도둑

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

BOJ - 보석 도둑

문제 유형: 우선순위 큐, 정렬, 그리디, 투포인터

문제 난이도: Gold II

시간 제한: 1초

메모리 제한: 256MB

 

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

풀이

O(n*k)로는 TLE가 난다는걸 알 수 있다.

우선, 보석의 정보와 가방의 정보를 오름차순 정렬한다.

 

각 가방별로 반복하는데, 현재 가방의 크기보다 작거나 같은동안 보석의 포인터를 밀면서, 가능한 보석들의 밸류만 우선순위 큐에 담는다. 이미 담을 수 있는지에 대한 여부를 확인했기에, 크기는 우선순위 큐에 담을 필요가 없다.

이제, 현재 가방에서 담을 수 있는 최고 밸류의 보석을 담아 누적하면 된다.

참고로, 값의 크기를 보면 알겠듯이, 정답의 크기는 32비트 signed integer로는 부족하다.

코드

C++

#include <bits/stdc++.h>
#include <queue>
#define ll long long
#define pii pair<int, int>
using namespace std;

int n, k;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> k;

  vector<pii> gems;
  for (int i = 0; i < n; ++i) {
    int m, v;
    cin >> m >> v;
    gems.push_back({m, v});
  }

  vector<int> bags;
  for (int i = 0; i < k; ++i) {
    int c;
    cin >> c;
    bags.emplace_back(c);
  }

  sort(gems.begin(), gems.end());
  sort(bags.begin(), bags.end());
  priority_queue<int> pq;
  ll ans = 0;
  int j = 0;

  for (int i = 0; i < k; ++i) {
    int c = bags[i];
    while (j < n && gems[j].first <= c) {
      pq.push(gems[j].second);
      j++;
    }

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

  cout << ans << "\n";

  return 0;
}