[BOJ 1202] 보석 도둑 (Java)

문제

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

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

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

접근 방법

1. 문제를 보니 한 가방에 하나의 보석을 넣어야 합니다. 보석 하나마다 모든 가방을 비교하는 간단한 방법이 있지만 O(n^2) 효율을 가지기 때문에 최악의 경우 90억회 계산이 필요합니다.

2. 조금 더 효율적인 방식을 생각해 봅시다. 가방을 오름차순으로 정렬해 작은 가방부터 들어갈 수 있는 가장 높은 가치의 보석을 찾게끔 하면 어떨까요?

3. 가장 높은 가치의 보석을 찾기 위해서는 현재 담으려는 가방에 들어갈 수 있는 무게를 가진 보석들을 우선으로 처리해야 하는것을 알 수 있습니다.

4. 보석을 무게 기준으로 정렬하면 3번을 해결할 수 있지만 매번 첫 노드부터 가장 높은 가치의 보석을 찾기엔 효율적이지 않습니다.

5. 때문에 우리는 우선순위 큐를 만들어 현재 가방에 들어갈 수 있는 모든 보석들을 가격을 우선순위로 주입합니다. 그렇다면 다음 가방에 보석을 담을 때는 기존의 우선순위 큐에 현재 가방의 무게에 들어갈 수 있는 보석을 추가로 주입한 뒤 큐에서 poll()을 하면 최대 가격의 보석을 얻을 수 있습니다!

⚠️주의할 점⚠️

• 보석의 가격은 최대 100만, 보석과 가방의 개수는 최대 30만개 있을 수 있기 때문에 결과 값이 int형의 범위인 21억(대략)을 가볍게 넘길 수 있습니다. 때문에 long 자료형을 통해 값을 저장할 필요가 있습니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class JewelryThief {

    static class Jewelry{
        int weight;
        int price;

        public Jewelry(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        long result = 0;

        PriorityQueue<Jewelry> jewelries = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        PriorityQueue<Jewelry> canStole = new PriorityQueue<>((o1, o2) -> o2.price - o1.price);
        int[] bags = new int[k];

        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");
            jewelries.offer(new Jewelry(Integer.parseInt(input[0]), Integer.parseInt(input[1])));
        }

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

        for (int bag : bags) {
            while (!jewelries.isEmpty() && bag >= jewelries.peek().weight) {
                canStole.offer(jewelries.poll());
            }
            if (!canStole.isEmpty()) {
                result += canStole.poll().price;
            }
        }
        System.out.println(result);
    }
}

결과