[BOJ] 1202번 보석도둑

개요

우선순위 큐와 그리디 알고리즘을 이용한 문제

문제링크

코드

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Baekjoon1202 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        Jewelry[] jewelries = new Jewelry[n];
        int[] backpacks = new int[k];
        for (int i = 0; i < jewelries.length; i++) {
            st = new StringTokenizer(br.readLine());

            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            jewelries[i] = new Jewelry(w, v);
        }
        Arrays.sort(jewelries);

        for (int i = 0; i < backpacks.length; i++) 
            backpacks[i] = Integer.parseInt(br.readLine());
        Arrays.sort(backpacks);

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        long result = 0;
        int j = 0;
        for (int i = 0; i < backpacks.length; i++) {
            while(j < n && jewelries[j].weight <= backpacks[i]) {
                pq.add(-jewelries[j].value);
                j++;
            }
            if(!pq.isEmpty()) 
                result += Math.abs(pq.poll());
        }

        bw.write(result+"\n");
        bw.flush();
    }
}

class Jewelry implements Comparable<Jewelry>{
    int weight;
    int value;

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

    @Override
    public int compareTo(Jewelry o) {
        return this.weight - o.weight;
    }    
}

해결 과정

보석 도둑은 알고리즘에서 유명한 문제이다.

어떤 상황에서 최대 가격을 얻을 수 있을지 그리디 알고리즘으로 찾아야 한다.

알고리즘 수업에서 비슷한 문제에 대해 공부한 적이 있었는데 그 때는 보석을 무게당 가격으로 정렬해서 최대값을 찾았다. 그 문제는 보석을 잘라서 넣을 수 있었고 가방의 갯수 제한이 없었기 때문이다.

하지만 이 문제는 가져갈 수 있는 보석의 갯수가 제한되어 있고 가방에 담을 수 있는 보석의 무게도 제한되어 있다.

이럴 경우에는 보석을 무게를 기준으로 오름차순 정렬하고 가방도 오름차순 정렬해서 최대 무게가 작은 가방부터 채워나가면 된다.

그리고 특정 가방에 들어갈 수 있는 보석은 여러개가 있을 수 있으므로 최대 무게가 작은 가방부터 들어갈 수 있는 보석 중에 가장 큰 가격을 가진 보석을 넣어가면서 해결해 나가야 한다.

그럴려면 필요한 것이 우선순위 큐인데 들어 갈 수 있는 보석을 모두 우선순위 큐에 넣고 가장 큰 값을 먼저 나오게 함으로 위의 알고리즘을 수월하게 구현할 수 있다.

결과