[백준] 1202번 보석 도둑 (JAVA)

문제

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

1202번: 보석 도둑

 

설명

각 보석은 무게 M와 가격 V를 가지고 있다.
상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 C이다.
가방에는 최대 한 개의 보석만 넣을 수 있다.

먼저 보석의 무게와 가치를 저장할 Dia 클래스를 만든다. 가방마다 담을 수 있는 최대 무게가 있으므로 무게가 낮은 보석부터 넣으면서 판단하기 위해 무게를 기준으로 오름차순으로 정렬하도록 compareTo 메소드를 재정의한다. 그리고 보석과 가방의 정보를 저장할 배열을 만들어 각각 보석 무게 오름차순, 가방 용량 오름차순으로 정렬한다.

class Dia implements Comparable<Dia> {
    int weight;
    int price;

    public Dia(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }

    public int getPrice() {
        return price;
    }
        
    @Override
    public int compareTo(Dia d) {
        return weight - d.weight;
    }
}


Dia[] dias = new Dia[N];	// 보석 정보를 저장할 배열
/* 보석 정보 입력받음 */
Arrays.sort(dias);		// 보석 무게 오름차순 정렬
        
int[] bags = new int[K];	// 가방 정보를 저장할 배열
/* 가방 정보 입력받음 */
Arrays.sort(bags);		// 가방 용량 오름차순 정렬

가치가 높은 보석을 우선순위로 하는 우선순위 큐를 만든다.

가방을 하나 선택하고 선택된 가방에 넣을 수 있는 보석을 모두 우선순위 큐에 추가한다.

과정이 끝나면 우선순위 큐의 맨 앞에는 가장 비싼 보석이 있기 때문에 결과에 해당 보석의 가치를 더한다.

// 가치가 높은 보석 기준 우선순위 큐
PriorityQueue<Dia> pq = new PriorityQueue<>(Comparator.comparingInt(Dia::getPrice).reversed());

int diaIndex = 0;
long result = 0;

// 1. 남은 가방 중 제일 작은 가방을 선택 (정렬)
for (int i = 0; i < K; i++) {
    int currentBag = bags[i];

    // 2. 선택된 가방에 넣을 수 있는 남은 보석 중 가장 비싼 보석을 선택 (힙을 사용)
    while (diaIndex < N && dias[diaIndex].weight <= currentBag) {
        pq.add(dias[diaIndex++]);
    }

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

 

전체 코드

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

public class Main {

    static int N, K;
    static Dia[] dias;
    static int[] bags;

    static class Dia implements Comparable<Dia> {
        int weight;
        int price;

        public Dia(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }

        public int getPrice() {
            return price;
        }

        @Override
        public int compareTo(Dia d) {
            return weight - d.weight;
        }
    }

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

        dias = new Dia[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            dias[i] = new Dia(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

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

        // 보석 무게 오름차순 정렬
        Arrays.sort(dias);
        
        // 가방 용량 오름차순 정렬
        Arrays.sort(bags);

        // 가치가 높은 보석 기준 우선순위 큐
        PriorityQueue<Dia> pq = new PriorityQueue<>(Comparator.comparingInt(Dia::getPrice).reversed());

        int diaIndex = 0;
        long result = 0;

        // 1. 남은 가방 중 제일 작은 가방을 선택 (정렬)
        for (int i = 0; i < K; i++) {
            int currentBag = bags[i];

            // 2. 선택된 가방에 넣을 수 있는 남은 보석 중 가장 비싼 보석을 선택 (힙을 사용)
            while (diaIndex < N && dias[diaIndex].weight <= currentBag) {
                pq.add(dias[diaIndex++]);
            }

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

        System.out.println(result);
    }
}