[백준 1202번] 보석 도둑

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

 

package greedy;

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

public class Greedy1202 {

    static class Jewel {
        int weight;

        long value;

        public Jewel(int weight, long value) {
            this.weight = weight;
            this.value = value;
        }
    }

    static int N, K;

    static Jewel[] jewels;

    static long[] bag;

    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());

        jewels = new Jewel[N];
        bag = new long[K];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            jewels[i] = new Jewel(weight, value);
        }


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

        // 오름차순
        Arrays.sort(bag);
        Arrays.sort(jewels, (a, b) -> a.weight - b.weight);


        long result = simulation();
        System.out.println(result);
    }

    private static long simulation() {
        long result = 0;
        PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
        int idx = 0;
        for (int i = 0; i < K; i++) {
            long capacity = bag[i];


            while (idx < N && jewels[idx].weight <= capacity) {
                pq.add(jewels[idx].value);
                idx++;
            }

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

 

핵심은 먼저 보석의 무게를 오름차순으로 정렬하고, 가방의 무게도 오름차순으로 정렬하는 것이다. 이후 각 가방을 순서대로 확인하면서 해당 무게에 담을 수 있는 보석들을 넣는다. 이 과정에서 while 문을 이용해 조건에 맞는 보석을 처리하고, 루프가 끝나면 바로 꺼내주는 방식으로 진행한다.

또한, 보석의 가격 합이 매우 커질 수 있으므로 반드시 long 타입으로 선언해야 한다.