[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)

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

 

출력

 

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

 

정답

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

class Main {
    // n 보석 개수, k 가방 개수, c 가방 무게
    static int n, k;
    static int[][] jewelry;
    static int[] bags;
    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());

        jewelry = new int[n][2];
        bags = new int[k];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            jewelry[i][0] = Integer.parseInt(st.nextToken());
            jewelry[i][1] = Integer.parseInt(st.nextToken());
        }

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

        Arrays.sort(jewelry, Comparator.comparingInt(o -> o[0]));
        Arrays.sort(bags);

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        long totalPrice = 0;
        int index = 0;
        for (int i = 0; i < k; i++) {

            while (index < n && jewelry[index][0] <= bags[i]) {
                pq.add(jewelry[index][1]);
                index++;
            }

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

        System.out.println(totalPrice);
    }
}

 

여기서 고민했던 부분은 제일 비싼 보석을 담아야되는데 어떻게 담아야될지 고민하는 부분이였다. 0번 index에서 조건에 만족하는 보석 무게를 가방에 넣고 거기서 가장 큰 값을 추출하면 중복 없이 처리가 가능하다