[백준]1202 보석도둑

1202번: 보석 도둑 (acmicpc.net)

1202번: 보석 도둑

문제

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

상덕이가 털 보석점에는 보석이 총 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)

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

 

내풀이

딱 봤을 때 이미 많이 풀었던 knapsack 문제인가 싶기도 했는데, 가방을 여러개 주는데 가방에 최대 한개의 보석을 넣을 수 있다 라는 점에서 그리디의 냄새가 나서 

가방의 무게가 작은 경우 부터 최대의 가치의 보석을 챙겨가는 방식으로 해결하면 되겠다는 생각을 했다 

여기까지 접근은 정답을 알고 봤을 때 완벽한 접근이였다.

다만 한번에 문제를 해결하지 못한 부분이 가방의 무게를 초과하지 않는 보석들 중에서 어떻게 최대의 가치의 보석을 효율적으로 찾을 것이냐 였다.

이부분에서 괜찮은 방법이 생각나지 않아 그냥 브루트 포스하게 탐색을 하여 이중 for문을 시도하니 시간 초과가 났다.

 

답을 찾아보니 다른사람은 우선 순위큐를 사용하여 해결하였는데, 괜찮은 것 같아 적용하였다.

우선 순위큐를 활용하면 이전에 탐색했던 보석을 탐색하지 않아도 되어 훨씬 효율적으로 탐색할 수 있었다.

 

무게 1의 가방일 때 무게 1까지의 보석들의 가치를 비교하고, 무게 2의 가방일 때 다시 무게 1~2인 보석들의 가치를 비교하던 과정을 

무게 1의 가방일 때 무게 1까지의 보석들을 가치를 비교하면서 우선순위큐에 넣고 큐의 맨 위에 있는 보석을 꺼내고 

무게 2의 가방일 때는 무게 2인 보석들을 우선순위큐에 넣으면 이미 1인 보석들끼린 자리를 잡고 있고 무게가 2인 보석들만 비교하며 정렬되고 큐에서 또 맨 위에 있는 보석을 꺼내면 무게 1~2에서 가장 가치있는 보석을 꺼낼 수 있다.

 

import java.io.*;
import java.util.*;
public class Main {
    static BufferedReader input;
    static StringBuilder output = new StringBuilder();
    static String src = "3 2\n" +
            "1 65\n" +
            "5 23\n" +
            "2 99\n" +
            "10\n" +
            "2";

    static int N, K, jewelleryData[][],bag[];

    public static void main(String[] args) throws IOException {

        input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        //풀이

        StringTokenizer str = new StringTokenizer(input.readLine());
        N = Integer.parseInt(str.nextToken()); // 보석갯수
        K = Integer.parseInt(str.nextToken()); // 가방 개수

        bag = new int[K];

        jewelleryData = new int[N][2];
        for (int i = 0; i < N; i++) {
            str = new StringTokenizer(input.readLine());
            jewelleryData[i][0] = Integer.parseInt(str.nextToken());
            jewelleryData[i][1] = Integer.parseInt(str.nextToken());
        }

        Arrays.sort(jewelleryData, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o2[1] - o1[1];
                }
                return o1[0] - o2[0];
            }
        });
        for (int i = 0; i < K; i++) {
            bag[i] = Integer.parseInt(input.readLine());
        }
        Arrays.sort(bag);

        // 가방에 1개의 보석을 넣을 수 있고 가방의 무게가 정해져있으니 가방의 무게에 맞게 그리디한 탐색을 하면 될거같은 느낌?
        System.out.println(sol());
    }

    public static long sol() {
        long answer = 0;
        int idx = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < bag.length; i++) {
            //범위 내이고, 보석보다 가방의 무게가 더 크면
            while (idx < N && bag[i] >= jewelleryData[idx][0]) {
                pq.add(jewelleryData[idx++][1]); //
            }
            if (!pq.isEmpty()) {
                answer += pq.poll();
            }
        }

        return answer;
    }
}