백준 1202 (보석 도둑) - java

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

1202번: 보석 도둑

문제

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

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

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

 

유형 : 정렬 + 우선순위 큐 + 그리디

 

접근

• 굉장히 유명한 문제이고 어려운 문제이다. 보석과 가방을 각각 정렬해야 하는데 정렬 기준부터 많은 고민이 필요한 문제이다.
  • 가방 : 무게의 오름 차순 정렬
    • 가방을 오름차순으로 정렬하여 작은 것부터 탐색해야 하는 것은 쉽게 생각할 수 있다.
  • 보석 : 무게의 오름차순 + 가격의 내림 차순
    • 처음 접근했을 때 가격의 내림 차순 + 무게의 오름차순으로 접근하였지만 나중에 탐색시 O(N^2)의 시간 복잡도로 인해 문제를 해결하지 못했다.
  • 내림 차순 + 무게 오름차순 시 
    • 왜냐하면 이전 가방에 넣었던 보석이 다음 가방으로 들어갈 수 있고 이전에 가방에 넣지 않았지만 다음 가방에 들어가는 경우도 있을 수 있기 때문이다.
• O(N) 도출
  • 우선 내림차순의 우선순위 큐를 하나 생성한다.
  • 보석을 탐색하면서 해당 가방 무게안에 들어갈 수 있다면 빼도록 하여 가장 큰 가치의 값을 정한다.
  • i번째 가방에 들어갈 보석을 정했다면 나머지 보석들(우선순위에 저장한 이전 보석 + 무게가 커서 가방에 들어가지 못한 보석)을 다음 i+1번째 가방에서 탐색한다.

전체 코드

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

public class Main {
    static int n = 0;
    static int k = 0;

    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());

        PriorityQueue<Node> dia = new PriorityQueue<>(
                (x, y) -> {
                    if (x.m == y.m)
                        return y.v - x.v;

                    return x.m - y.m;
                }
        );

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            dia.add(new Node(m, v));
        }


        int[] bag = new int[k];
        for (int i = 0; i < k; i++) {
            bag[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(bag);


        PriorityQueue<Integer> pq = new PriorityQueue<>(
                Comparator.reverseOrder()
        );

        long result = 0;

        for (int i = 0; i < k; i++) {

            while (!dia.isEmpty() && dia.peek().m <= bag[i]) {
                Node cur = dia.poll();
                pq.add(cur.v);
            }

            if (!pq.isEmpty()) {
                result += pq.poll();
            }

        }


        System.out.println(result);
        br.close();
    }
}
class Node{
    int m;
    int v;

    Node(int m,int v){
        this.m = m;
        this.v = v;
    }
}