[BOJ] 1202 보석 도둑 - JAVA

1. 문제

1202번: 보석 도둑

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

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

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

---

2. 풀이

pq를 이용해 현재 가방에 넣을 수 있는 보석 중 가장 값어치 있는 것만 뽑아내는 방식이다.

입력 및 정렬

보석과 가방 모두 무게순으로 오름차순 정렬한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());

ArrayList<int[]> jewel = new ArrayList<>();
for(int i=0;i<N;i++){
   st = new StringTokenizer(in.readLine());
   jewel.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
}
Collections.sort(jewel,(o1, o2) -> o1[0]-o2[0]);

int[] backpack = new int[K];
for(int i=0;i<K;i++) backpack[i] = Integer.parseInt(in.readLine());
Arrays.sort(backpack);

 

탐색

가격으로 내림차순 정렬되는 pq를 만든다.

last는 pq에 넣지 않은 보석의 위치다.

가방을 무게 순으로 탐색하면서, 현재 가방에 last위치 보석을 넣을 수 있다면 pq에 넣고 last+1한다.

pq에는 현재 가방에 담을 수 있는 보석이 담겨져 있다. answer에 pq의 첫번째 보석 가격을 더한다.

 

탐색이 끝난 후에 answer을 출력한다.

long answer = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]);
int last = 0;
for(int i=0;i<K;i++){
   while(last < N && backpack[i] >= jewel.get(last)[0]){
      pq.offer(jewel.get(last++));
   }
   if(!pq.isEmpty()) answer += pq.poll()[1];
}

System.out.println(answer);

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_1202_보석도둑 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());

      ArrayList<int[]> jewel = new ArrayList<>();
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         jewel.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
      }
      Collections.sort(jewel,(o1, o2) -> o1[0]-o2[0]);

      int[] backpack = new int[K];
      for(int i=0;i<K;i++) backpack[i] = Integer.parseInt(in.readLine());
      Arrays.sort(backpack);

      long answer = 0;
      PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]);
      int last = 0;
      for(int i=0;i<K;i++){
         while(last < N && backpack[i] >= jewel.get(last)[0]){
            pq.offer(jewel.get(last++));
         }
         if(!pq.isEmpty()) answer += pq.poll()[1];
      }

      System.out.println(answer);
   }
}

---

3. 결과

pq에 보석을 모두 넣고 가능한 가방 위치를 lower_bound 찾는 방식으로 이분탐색을 진행했더니 시간초과가 났다.

이 문제는 보석 기준이 아니라 가방 기준으로 풀어야되는 문제였던 것 같다.