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

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

1202번: 보석 도둑

문제

풀이

처음엔 한 가방에 하나의 보석밖에 못넣는다고 적힌것 못 보고 Knapsack 문제 + 가방이 여러개 ..? 라고 접근할 뻔 했다가 산으로 갈 뻔 했다..

접근방법
용량이 작은 가방과 무게가 작은 보석 순으로 천천히 순차적으로 보고 , 조건에 맞으면 그 가방에 보석을 넣는 방식으로 하면 된다. => 그리디 접근

가령 , 예제 2 의 (1,65) (2,99) 라는 보석을 용량2의 가방에 넣을 때 우선 가방에 들어지는지 아닌지 판단을 하고 
두 보석중 가치가 큰 보석을 넣으면 된다는 것.
(2,99) 보석을 넣고 남은 (1,65) 보석은 그 다음 차례의 가방과 이 가방에 들어갈 보석을 또 검사할 때 가치가 더 높은 보석을 넣어주는 식으로해서 가방을 다 쓸때 까지 반복하면 끝

arr : 보석 , bag : 가방, index : 보석 인덱스
q : 가치순으로 정렬한 우선순위 큐

 

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,K;
    static int[][] arr;
    static int[] bag;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        N = input[0]; K = input[1];
        arr = new int[N][2]; bag = new int[K];
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for(int i=0;i<N;i++)
            arr[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
        for(int i=0;i<K;i++) bag[i] = Integer.parseInt(br.readLine());
 
        Arrays.sort(arr,(o1,o2)->o1[0]-o2[0]);
        Arrays.sort(bag);
 
        long sum=0;
        int index=0;
        for (int curBag : bag) {
 
            while (index < N && arr[index][0]<=curBag )
                q.add(arr[index++][1]);
 
            if(q.size()>0) sum+=q.poll();
        }
        System.out.println(sum);
 
    }
}