[BOJ] 1202. 보석 도둑 (🥇, 그리디)

🔗

풀이

비싼 쥬얼리부터 가방에 담아야 한다. 근데 이때 최대한 효율적으로 가방에 담아야 한다. 비싼 순서대로 정렬한 다음에 쥬얼리의 무게와 가장 차이가 나지 않는 가방에 담으려고 했는데 그렇게 되면 예제2에서 (2, 99)의 보석이 2 크기의 가방에 담기게 되고, (1, 65)의 보석을 담을 수 없게 된다.

결국 최대한 많은 보석을 담기 위한 효율적인 방법을 생각해야 한다. 가방 하나에는 보석을 하나밖에 담을 수 없기 때문에 가방에 보석을 담을 때, 다른 보석들이 가방에 들어갈 기회를 최대한 많이 줄 수 있는 보석을 가방에 담아야 한다.

만약 무게는 작은데 가격이 높게 나가는 보석을 가장 크기가 큰 가방에 담게 되면, 이후에 무게가 무거운 보석들은 가방에 담길 기회가 없을 수 있다. 작은 가방에 담길 수 있는 보석은 큰 가방에 담길 수 있지만, 큰 가방에만 담길 수 있는 보석들은 작은 가방에 담길 수 없다. 결국 작은 가방에 담을 수 있는 보석들은 최대한 작은 가방에 담아야 하는 것이다. 그래서 그리디한 풀이가 된다.

크기가 n인 가방에 보석들을 담을 때, 최대한 비싼것부터야 담아야 하는데 이때 보석 개수는 최대 30만이기 때문에 일반 정렬로 구하게 되면 최악의 경우 O(N^2)이 되기 때문에 힙 정렬을 사용하는 우선순위 큐를 사용해서 해당 크기의 가방에 담을 수 있는 보석들 가운데 가장 비싼 보석을 찾아 담는다.

먼저 보석들을 무게 순서대로 오름차순 정렬하고, 가방도 오름차순 정렬한다. 작은 가방에 담길 수 있는 보석들만 우선순위 큐에 담고, 그 중에서 가장 무거운 보석을 꺼낸다. 해당 과정을 반복한다.

// 보석 도둑

package Baekjoon.Gold;

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

public class baekjoon_1202 {
        public static void main(String[] args) throws IOException {
        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());

        long[][] jewelry = new long[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewelry[i][0] = Long.parseLong(st.nextToken());
            jewelry[i][1] = -Long.parseLong(st.nextToken());
        }

        long[] bags = new long[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Long.parseLong(br.readLine());
        }

        Arrays.sort(jewelry, (a, b) -> (int) (a[0] - b[0]));
        Arrays.sort(bags);

        long answer = 0;
        int idx = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(arr -> arr[1]));
        for (int i = 0; i < K; i++) {
            long bagWeight = bags[i];
            while (idx < N && bagWeight >= jewelry[idx][0]) {
                pq.add(jewelry[idx]);
                idx++;
            }

            if (!pq.isEmpty()) {
                answer -= pq.poll()[1];
            }
        }
        System.out.println(answer);
    }
}