[백준] 1202번: 보석도둑 -JAVA

 

문제 바로가기 > 1202번: 보석도둑

 

얼핏보면 냅색 알고리즘이여서 DP를 이용해야 할것 같지만 가방에는 최대 한 개의 보석만 넣을 수 있다는 조건이 있다.

그리디 알고리즘과 우선순위 큐를 사용하여 풀 수 있는 문제이다.

 

모든 가방에 대해 모든 보석을 검사하면 위 문제를 해결할 수 있으나, N과 K는 최대 30만이기때문에 O(9 x 10^10)으로 시간 초과가 난다. 따라서 O(N^2)보다 줄이기 위해서 우선순위 큐 자료구조를 이용해야 한다.

1. 보석은 무게에 대해 오름차순 정렬하되, 무게가 같을 경우 가격에 대해 내림차순 정렬한다.
2. 가방은 오름차순 정렬한다.
3. 모든 가방에 대해서 반복문을 수행한다.
   1. 특정 가방의 무게보다 작은 보석의 가격을 모두 우선순위 큐에 집어넣는다. (이때, 우선순위 큐는 가격에 대해 내림차순 정렬을 해야한다.)
   2. 우선순위 큐가 비어있지 않다면, 우선순위 큐에서 맨 앞 요소를 하나 빼고 그 가격을 더해간다.

 

import javax.swing.*;
import java.io.*;
import java.util.*;

public class _1202 {
    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()); //가방 개수

        List<Jewelry> jewelries=new ArrayList<>();
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            int w=Integer.parseInt(st.nextToken());
            int p=Integer.parseInt(st.nextToken());
            jewelries.add(new Jewelry(w,p));
        }
        Collections.sort(jewelries, (o1, o2) -> {
            if(o1.weight==o2.weight){
                return o2.price-o1.price;
            }
            return o1.weight-o2.weight;
        });

        PriorityQueue<Integer> priceQue=new PriorityQueue<>(Comparator.reverseOrder());


        ArrayList<Integer> bags=new ArrayList<>();
        for(int i=0;i<k;i++){
            st=new StringTokenizer(br.readLine());
            int w=Integer.parseInt(st.nextToken());
            bags.add(w);
        }
        Collections.sort(bags);
        long sum=0;
        for(int i=0, j=0;i<k;i++){
            while(j<n&&jewelries.get(j).weight<=bags.get(i)){
                priceQue.add(jewelries.get(j).price);
                j++;
            }
            if(!priceQue.isEmpty()){
                sum+=priceQue.poll();
            }
        }
        System.out.println(sum);

    }
    public static class Jewelry{
        public int weight;
        public int price;
        public Jewelry(int weight, int price){
            this.weight=weight;
            this.price=price;
        }
    }


}