b1202. 보석도둑

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

 

 

보석의 무게와 가치, 가방의 용량이 주어졌을 때 가방에 단하나의

보석이 들어간다고 가정한다면 입력에 따라 최대 얼마만큼의 가치를 담을수

있는지 구하는 문제였다.

 

우선 보석의 무게와 가치를 저장하고 무게에 따라 그리고 가치에 따라 정렬해야할

필요성을 느꼈다. 그리하여 jewelry라는 class를 만들고 그 자료형으로 array를 만들었다.

 

이후 무게를 기준으로 오름차순으로 정렬하되 무게가 같다면 가치가 높은 순서대로

내림차순 정렬하도록 하였다.

 

이후 가방의 용량을 input[] array에 입력받고 오름차순 정렬한 후

priority queue를 활용하여 낮은 무게부터 확인해가며 보석을 모두 집어넣기 시작했다.

 

이후 가방의 용량을 하나씩 올릴때마다 pq에서 하나씩 빼며 answer에 값을 더하였고

최종 무게가 answer였으므로 출력하여 문제를 해결하였다.

 

 

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

public class Main {
    private static Jewelry[] j;
    private static int[] input;
    private static class Jewelry{
        int cost;
        int price;
        public Jewelry(int cost, int price){
            this.cost = cost;
            this.price = price;
        }
    }
    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());
        j = new Jewelry[N];
        input = new int[K];
        long answer = 0;
        for(int i = 0 ; i < N ; i++){
            st = new StringTokenizer(br.readLine());
            j[i] = new Jewelry(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(j,(o1,o2)->{
            if(o2.cost == o1.cost)
                return o2.price - o1.price;
            return o1.cost-o2.cost;
        });
        for(int i = 0 ; i < K ; i++ ){
            input[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(input);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for(int i = 0, l = 0; i < K ; i++){
            while(l < N && j[l].cost<=input[i]){
                pq.offer(j[l++].price);
            }
            if(!pq.isEmpty()){
                answer += pq.poll();
            }
        }
        System.out.println(answer);
    }
}