백준 #1202 보석 도둑

이번 문제는 knapsack 문제라고 볼 수 있는데, 전혀 다른 문제네요.  그래도 탐욕 알고리즘을 적용하기 위해서 방법을 강구해야 합니다.

난이도는 Gold II 문제입니다.  정답률 23%로 상당히 낮습니다.  왜 틀릴까 생각했었는데, 틀린 이유들을 보면, 짐작이 갑니다.

 

Jewel Thief

 

K개의 가방에 보석을 1개씩만 넣을 수 있는데, 각 가방에는 최대 넣을 수 있는 보석의 무게가 정해져있습니다.  보석에 무게와 값이 주어질 때, 가장 값어치가 높게 보석을 챙겨올 때, 그 값어치를 구하라는 문제입니다.

 

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

1202번: 보석 도둑

이 문제는 정렬과 힙을 사용해야 합니다.  힙을 사용하지 않고 다른 방법을 사용해도 되긴하겠지만, 예를 들어서 set 같은 것이요.  그런데, set을 써서 틀린 분들이 있습니다.  한계무게가 같은 가방들이 많아서겠죠.

 

일단, 보석들과 가방들을 무게별로 정렬합니다.  그런 후에, 한계무게가 가장 가벼운 가방부터 그 가방에 들어갈 수 있는 보석들을 힙에 밀어넣습니다.  완료가 되면, 가장 값어치가 비싼 보석을 하나 뺍니다.  그것을 현재 가방에 넣으면 됩니다.  힙은 초기화없이 가방의 한계무게에 따라 계속 밀어넣어주면 됩니다.

 

시간초과가 되는 분들도 많은데, 기본적으로 이 알고리즘을 사용하면, \(O(2 N \log N + K \log K)\) 으로 복잡도가 좀 복잡하게 나옵니다.  각각 정렬하는 것과 힙에 보석들을 넣고 빼는 복잡도입니다.  N과 K가 최대치라고 해도 특별하게 시간초과는 날 수 없는 알고리즘입니다.

 

전, 힙을 직접 사용 안하고 우선순위 큐를 이용해서 구현했습니다.  어차피 우선순위 큐가 힙을 이용해서 제작되었기 때문에, 편한 방법을 이용했습니다.

 

틀리신 분들 보면, 이 문제에서 숫자 범위를 살펴봐야 합니다.  K가 최대 300,000 이고, 보석 값어치가 최대 1,000,000이므로 나올 수 있는 값은 최대 \(3 \times 10^{11} \)으로 int 범위를 벗어납니다.

 

제가 작성한 소스입니다.  참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1202 - Jewel Thief
//    - by Aubrey Choi
//    - created at 2020-01-07
//----------------------------------------------------------
#include <stdio.h>
#include <queue>
#include <algorithm>

struct Jewel { int m, v; } jw[300000]; int b[300000];
int main()
{
  int n, k, i, j; long long r=0;
  std::priority_queue<int> q;
  scanf("%d%d",&n,&k);
  for(i=0;i<n;i++) scanf("%d%d",&jw[i].m,&jw[i].v);
  std::sort(jw,jw+n,[](Jewel &a,Jewel &b){return a.m<b.m;});
  for(i=0;i<k;i++) scanf("%d",b+i);
  std::sort(b,b+k);
  for(i=0,j=0;i<k;i++)
  {
    for(;j<n&&jw[j].m<=b[i];j++) q.push(jw[j].v);
    if(q.empty()) continue;
    r+=q.top(); q.pop();
  }
  printf("%lld\n",r);
}