[백준 / 골드2] 1202 보석 도둑 (Java)

문제 보기

사용한 것

• 훔칠 수 있는 보석의 최대 가격을 구하기 위한 그리디
• 가방에 넣을 수 있는 보석 중 가장 큰 가치를 고르기 위한 우선순위 큐

풀이 방법

• items에 보석들을 무게 오름차순, 무게가 같으면 가치 내림차순으로 저장한다.
• bags에 가방의 무게 오름차순으로 저장한다.
• 훔칠 수 있는 보석들 중 가장 큰 가치의 보석을 빼내기 위한 pq를 사용한다.
• 반복문을 돌며 현재 가방에 들어갈 수 있는 보석들을 pq에 넣는다.
• 더 이상 가방에 들어갈 수 있는 보석들이 없다면 pq에서 가장 큰 가치의 보석을 하나 빼내어 answer에 더한다.
• 다음 가방의 경우 이전 가방보다 무게가 크기 때문에 이미 pq에 저장된 보석들도 무조건 가방에 들어갈 수 있다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);

        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");
            int m = Integer.parseInt(line[0]);
            int v = Integer.parseInt(line[1]);
            items[i] = new Item(m, v);
        }

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

        Arrays.sort(items);
        Arrays.sort(bags);

        long answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        int j = 0;
        for (int i = 0; i < k; i++) {
            while (j < n && items[j].m <= bags[i].c) {
                pq.offer(items[j++].v);
            }

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

        System.out.println(answer);
    }
}

class Item implements Comparable<Item> {

    public int m;
    public int v;

    public Item(int m, int v) {
        this.m = m;
        this.v = v;
    }

    @Override
    public int compareTo(Item o) {
        if (this.m == o.m) {
            return o.v - this.v;
        } else {
            return this.m - o.m;
        }
    }
}

class Bag implements Comparable<Bag> {

    public int c;

    public Bag(int c) {
        this.c = c;
    }

    @Override
    public int compareTo(Bag o) {
        return this.c - o.c;
    }
}