[백준] 1202번(Java)

📖 요세푸스 문제 0

[ 문제 ]
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 $N$개 있다. 각 보석은 무게 $M_i$와 가격 $V_i$를 가지고 있다. 상덕이는 가방을 $K$개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 $C_i$이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

💡풀이

• 보석을 무게의 오름차순으로 우선 정렬
• 가방을 최대 무게 오름차순으로 정렬
• PriorityQueue 하나 선언
• 가방 무게를 하나하나 방문하면서 가방 무게보다 낮은 무게의 보석들을 하나씩 PriorityQueue에 담음
• 다 담았으면 그 중 제일 값어치가 비싼 무게 하나를 꺼내서 넣음
• 만약 방문한 가방 무게에서 PriorityQueue에 추가할 보석이 없다면, 이전에 추가한 보석들 중 제일 값어치가 비싼 보석을 추가하면 됨
• 로직은 너무 단순한데... DFS 써보고 난리도 아니었던 문제

    package priority_queue;

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.*;

    public class bj1202_1 {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static int N, K;
        static ArrayList<int[]> arr;
        static ArrayList<Integer> backpack;

        public static void main(String[] args) throws IOException {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            arr = new ArrayList<int[]>();
            backpack = new ArrayList<Integer>();

            for(int i = 0 ; i < N ; i ++){
                StringTokenizer st1 = new StringTokenizer(br.readLine());
                int M = Integer.parseInt(st1.nextToken());
                int V = Integer.parseInt(st1.nextToken());
                arr.add(new int[] {M, V});
            }

            for(int j = 0 ; j < K ; j ++){
                int c = Integer.parseInt(br.readLine());
                backpack.add(c);
            }

            arr.sort((a, b) -> a[0] - b[0]);
            backpack.sort(Comparator.naturalOrder());

            int cur = 0;
            long maxRob = 0;

            PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
            for(int a = 0 ; a < K; a ++){

                while(cur < arr.size() && arr.get(cur)[0] <= backpack.get(a)){
                    pq.add(arr.get(cur)[1]);
                    cur ++;
                }

                if(!pq.isEmpty()){
                    maxRob += pq.poll();
                }
            }
            System.out.println(maxRob);
        }
    }

https://www.acmicpc.net/problem/1202