[백준] 보석 도둑 1202번 Java

문제 링크

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

알고리즘: 그리디

문제

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

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

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

풀이

보석을 담을 수 있는 가방이 여러 개라면 그중 가장 적은 수용량을 가진 가방을 우선적으로 넣어줘야 최댓값을 만들 수 있다.
일단 보석과 가방을 하나의 배열에 넣고 가방의 가격은 -1로 설정한다.
정렬은 무게가 낮은 순 같으면 가격이 높은 순으로 정렬한다.
이렇게 해야 보석과 가방이 같은 무게일 때 가방이 제일 뒤에 위치하게 된다.
그리고 가방 + 보석이 담긴 배열을 하나씩 확인하면서 보석이면 가격을 우선순위로 하는 큐에 넣어주고 가방이 나오면 우선순위 큐에서 하나 poll(반환,삭제) 해주고 반환 값은 ans에 +해준다. for 문이 끝났다면 ans에는 최댓값이 들어있게 된다.

소스 코드

import java.io.*;
import java.util.*;
class JewBag implements Comparable<JewBag> {
    int w,p;
    public JewBag(int w, int p) {
        this.w = w;
        this.p = p;
    }
    
    @Override
    public int compareTo(JewBag v) {
        int dif = this.w - v.w;
        if(dif>0) return 1;
        if(dif<0) return -1;
        if(dif == 0) {
            int p_dif = v.p - this.p;
            if(p_dif>0) return 1;
            if(p_dif<0) return -1;
        }
        return 0;
    }
}

public class Main {
    static int N,K;
    static long ans = 0;
    static int bag_cout = 0;
    static JewBag jew_bag[];
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());
      jew_bag = new JewBag[N+K];
      for(int i=0; i<N+K; i++) {
          if(i<N) {
              StringTokenizer sti = new StringTokenizer(br.readLine());
              int jw = Integer.parseInt(sti.nextToken());
              int jp = Integer.parseInt(sti.nextToken());
              jew_bag[i] = new JewBag(jw,jp);
          } else {
              int bw = Integer.parseInt(br.readLine());
              jew_bag[i] = new JewBag(bw,-1);
          }
      }
      Arrays.sort(jew_bag);
      PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
      for(int i=0; i<jew_bag.length; i++) {
          if(jew_bag[i].p == -1) {
              //가방이 나오면 보석 가격순 우선순위 큐에서 poll.
              if(!priorityQueue.isEmpty()) {
                  ans += priorityQueue.poll();
              }
              bag_cout += 1;
          } else {
              //보석이 나오면 보석 가격순 우선순위 큐에 삽입.
              priorityQueue.add(jew_bag[i].p);
          }
          if(bag_cout == K) break;
      }
      System.out.println(ans);
    }
}