[백준/BOJ] 1202 보석 도둑- JAVA

[백준/BOJ] 1202 보석 도둑- JAVA

문제

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

 

문제 분석

조건

N개의 보석이 각각의 무게와 가격을 가지고 있고, K개의 가방이 각각의 최대 허용 무게를 가지고 있다. 각 가방에는 최대 한 개의 보석만 넣을 수 있을 때, 훔칠 수 있는 보석의 최대 가격을 구하는 문제이다.

풀이방법

가장 작은 가방부터 넣을 수 있는 보석 중 가장 가치가 큰 보석을 넣는 그리디 방식으로 해결했다.

가장 먼저 보석은 무게가 가벼운 순으로, 가방은 담을 수 있는 용량이 작은 순으로 정렬한다.

그다음, 용량이 가장 작은 가방부터 순서대로 확인하며 현재 가방에 담을 수 있는 무게의 보석들을 모두 찾아낸다.

이렇게 찾아낸 보석들은 정답이 될 수 있는 후보군이므로, 이 보석들의 가치만을 가격이 높은 순으로 정렬되는 우선순위 큐에 저장해둔다.

현재 가방에 넣을 수 있는 모든 보석을 후보로 정리하였으면 후보들 중 가장 가치가 높은 보석을 골라 담는다.

다음으로 더 큰 가방을 확인할 때에도 이 우선순위 큐를 비우지 않는데, 이는 이전에 후보였던 보석들이 당연히 더 큰 가방에도 들어갈 수 있기 때문이다.

코드

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

class Gem implements Comparable<Gem> {
    private int m;
    private int cost;

    public Gem(int m, int cost) {
        this.m = m;
        this.cost = cost;
    }

    public int getM() {
        return m;
    }

    public int getCost() {
        return cost;
    }

    /**
     * 무게 기준 오름차순
     */
    @Override
    public int compareTo(Gem o) {
        return this.m - o.m;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());   //보석 수
        int K = Integer.parseInt(st.nextToken());   //가방 수

        // 보석 입력받아 무게 가벼운 순으로 정렬
        PriorityQueue<Gem> gems = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            gems.offer(new Gem(m, v));
        }

        // 가방 입력, 작은 순으로 정렬
        int[] bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(bags);

        long answer = 0;
        // 가방에 넣을 수 있는 보석 후보들의 가격(내림차순)
        PriorityQueue<Integer> cost = new PriorityQueue<>(Comparator.reverseOrder());
        for (int bag : bags) {  // 작은 가방부터
            while (!gems.isEmpty() && gems.peek().getM() <= bag) {  
            	// 지금 가방에 들어갈 수 있는 보석들 전부 가격 후보에 넣기
                cost.offer(gems.poll().getCost());
            }
            if (!cost.isEmpty()) {  // 후보 중 가장 가치 높은 보석 답에 넣기
                answer += cost.poll();
            }
        }
        System.out.println(answer);
    }
}