보석 도둑

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

풀이

보석에는 무게와 가치가 있고 배낭에는 담을 수 있는 무게 제한이 있다.

배낭에는 보석 하나만을 담기 때문에 생각을 잘 해야한다. 무조건 비싼 보석을 배낭에 넣다가는 베스트 케이스를 찾지 못하는 문제가 있다. 그렇기 때문에 배낭의 무게 제한도 고려를 해야한다.

그래서 먼저 보석들과 배낭을 무게를 기준으로 오름차순으로 정렬을 했다. 그래서 무게가 적게 나가지만 가치가 큰 보석을 제한이 작은 배낭에 우선적으로 할당할 수 있게 하였다.

이후 보석을 하나씩 꺼내 만약 이 보석이 배낭의 무게제한을 충족한다면 가치가 큰 순서로 우선 순위 큐에 넣어주고 보석을 다 찾았다면 우선 순위 큐의 제일 위에 있는 값을 sum에 더해주고 이 것을 배낭 개수만큼 반복하면 끝난다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    static int n, m, k;
    static int[] alpha;
    static String[] ins;
    static int max = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);


        ArrayList<Pair> jewel;

        jewel = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            jewel.add(new Pair(Integer.parseInt(line[0]), Integer.parseInt(line[1])));
        }

        // 무게 중심 정렬
        jewel.sort(Pair::compareTo);

        ArrayList<Integer> bag = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            bag.add(Integer.parseInt(br.readLine()));
        }
        bag.sort(Integer::compareTo);

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

        long sum = 0L;
        int idx = 0;
        for (int i = 0; i < k; i++) {
            while (idx < n && jewel.get(idx).w <= bag.get(i)) {
                priorityQueue.add(jewel.get(idx).p);
                idx++;
            }
            if (!priorityQueue.isEmpty())
                sum = sum + priorityQueue.poll();
        }

        bw.write(sum + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class Pair implements Comparable<Pair> {
    public int w;
    public int p;

    public Pair(int w, int p) {
        this.w = w;
        this.p = p;
    }


    @Override
    public int compareTo(Pair o) {
        return this.w - o.w;
    }
}