백준 1202번 - 보석 도둑

개인적으로 이번 문제와 같이 문제 1개에 다양한 알고리즘 및 자료구조를 활용하는 문제가 어려우면서도 좋은 문제인 것 같다. 여러번 볼 가치가 있는 문제라서 정리하려고 한다.

🎯 Logic

언뜻 보면 knapsack problem 인 것처럼 보이지만 문제를 제대로 읽게 되면 그렇지 않음을 알 수 있다.
이 문제에서의 핵심은 배낭이 K개이고 배낭마다 최대 1개의 보석을 담을 수 있고 최댓값을 구하라는 것이다.
보통 최댓값을 구하라고 할 때 흔히 생각해 볼 만한 알고리즘은 Greedy 혹은 DynamicProgramming 이다. 이 때 무게가 작은 배낭 1개마다 해당 무게보다 작거나 같은 보석들 중에 가치가 최대인 보석만을 계속 가져간다면 전체에서의 최댓값이 되지 않을까 라는 생각을 해볼 수 있다.

Greedy 알고리즘의 조건
1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

또한, 매 배낭마다 각 iteration마다 보석을 넣어가며 무게가 배낭 무게 보다 큰 보석이 나오면 멈추어서 가장 큰 가치를 가지는 보석을 빼내면 되기 때문에 우선순위 큐를 사용하면 적당함을 알 수 있다

풀이

package AlgorithmStudy.자료구조.힙.P1202;

// PriorityQueue 활용문제
// Greedy + 정렬 + PriorityQueue
// 1. 배낭 무게를 정렬
// 2. 정렬된 배낭 무게 보다 같거나 작은 보석 중 최대의 가치를 가지는 보석만 선택
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N,K;
    static int[][] jewelry;
    static int[] bags;
    static int answer=0;
    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());
        jewelry = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewelry[i][0] = Integer.parseInt(st.nextToken());
            jewelry[i][1] = Integer.parseInt(st.nextToken());
        }
        bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        // 1. 보석들에 대한 정렬
        // 2. 배낭 정렬
        Arrays.sort(jewelry, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        Arrays.sort(bags);

        // 정렬된 배낭 무게보다 작거나 같은 보석들 중 최대 가치 선택
        PriorityQueue<int[] > pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];  // 가치가 클수록 우선순위 앞으로 옴
            }
        });

        int index=0;
        for (int i = 0; i < K; i++) {
            while (index<N) {
                if(bags[i] < jewelry[index][0]) break;
                pq.add(jewelry[index++]);
            }
            if(!pq.isEmpty()) answer += pq.poll()[1];
        }
        System.out.println(answer);
        LinkedList<int[]> linkedList = new LinkedList<>(new Comparator<>(){
            
        });
    }
}