[백준 1202] 보석 도둑(Java)

문제 링크 : https://www.acmicpc.net/problem/1202

이 문제는 우선순위 큐를 이용하여 풀 수 있습니다. 이 문제의 핵심은 보석을 기준으로 가방을 탐색할 것인가, 가방을 기준으로 보석을 탐색할 것인가를 정하는 것입니다. 가방의 최대 무게가 굉장히 크기 때문에 보석을 기준으로 맞는 가방을 탐색하면 시간 초과가 발생할 수 있기 때문에 가방을 기준으로 알맞은 보석을 배치하는 방식으로 진행합니다.

여기서 핵심은 그리디 알고리즘을 적용하여 현재 가방의 크기보다 작거나 같은 보석들 중 가장 비싼 보석을 담는 방식을 적용하는 것입니다. 따라서 크게 3개의 우선순위 큐가 필요하며, 각각의 정렬 방식도 다 다릅니다.

1. 보석 우선순위 큐 : 보석의 무게 기준으로 오름차순 정렬하되 같은 무게일 경우 비싼 보석 순으로 정렬
2. 가방 우선순위 큐 : 가방의 무게를 오름차순으로 정렬
3. 실제 훔칠 보석을 구하는 우선순위 큐 : 비싼 보석 순으로 정렬

이후 작은 가방부터 진행하면서 현재 가방의 크기보다 무게가 작거나 같은 보석들을 3번 우선순위 큐에 저장합니다. 이후 3번 우선순위 큐의 peek값이 도둑이 훔쳐야 할 가장 비싼 보석이기 때문에 이를 체크합니다.

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        PriorityQueue<Jewelry> jewelries = new PriorityQueue<>(new Comparator<Jewelry>() {
            @Override
            public int compare(Jewelry o1, Jewelry o2) {
                if(o1.M == o2.M) return o2.V - o1.V;
                else return o1.M - o2.M;
            }
        });
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            jewelries.add(new Jewelry(M,V));
        }

        PriorityQueue<Integer> bags = new PriorityQueue<>();
        for(int i=0;i<K;i++){
            bags.add(Integer.parseInt(br.readLine()));
        }

        PriorityQueue<Jewelry> queue = new PriorityQueue<>(new Comparator<Jewelry>() {
            @Override
            public int compare(Jewelry o1, Jewelry o2) {
                return o2.V - o1.V;
            }
        });

        long res = 0;
        while(!bags.isEmpty()){
            int bag = bags.poll();

            while(!jewelries.isEmpty() && bag >= jewelries.peek().M){
                queue.add(jewelries.poll());
            }

            if(!queue.isEmpty()){
                res += queue.poll().V;
            }
        }
        System.out.println(res);
    }

    static class Jewelry {
        int M;
        int V;

        Jewelry(int M, int V){
            this.M = M;
            this.V = V;
        }
    }
}