[BJ]1202. 보석도둑

BJ 1202. 보석도둑

 

 

문제링크

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

1202번: 보석 도둑

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/QgHV5h8kZuk

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2023. 1. 13.
 * @see https://www.acmicpc.net/problem/1202
 * @git
 * @youtube
 * @performance 121416 1104
 * @category #자료구조, #PQ, #PriorityQueue, #우선순위큐
 * @note
 */

public class BJ_G2_01202_보석도둑 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;

    static int N, K;
    static PriorityQueue<Jewelry> jewelries;
    static int[] bags;
    static PriorityQueue<Integer> pq;
    // 300000 * 1000000 ==> long
    static long A;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());

        jewelries = new PriorityQueue<>();
        for (int n = 0; n < N; n++) {
            tokens = new StringTokenizer(input.readLine());
            int m = Integer.parseInt(tokens.nextToken());
            int v = Integer.parseInt(tokens.nextToken());
            jewelries.offer(new Jewelry(m, v));
        }
        //System.out.println(Arrays.toString(jewelries));

        bags = new int[K];
        for (int k = 0; k < K; k++) {
            bags[k] = Integer.parseInt(input.readLine());
        }
        Arrays.sort(bags);

        //System.out.println(Arrays.toString(bags));
        // 가방을 순회 하면서 그 가방에 담을 수 있는 보석들을 관리! --> 가치를 기준으로 내림차순(비싼 것 부터)
        pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int k = 0; k < K; k++) {
            for (; !jewelries.isEmpty() && jewelries.peek().m <= bags[k];) {
                pq.offer(jewelries.poll().v);
            }
            if (!pq.isEmpty()) {
                // 그 보석을k 번째 가방에 담자!
                A += pq.poll();
            }
        }
        System.out.println(A);
    }

    static class Jewelry implements Comparable<Jewelry> {
        int m, v;

        public Jewelry(int m, int v) {
            this.m = m;
            this.v = v;
        }

        @Override
        // 무게에 대한 오름차순
        public int compareTo(Jewelry o) {
            return Integer.compare(this.m, o.m);
        }

        @Override
        public String toString() {
            return "Jewelry [m=" + m + ", v=" + v + "]";
        }
    }

    // REMOVE_START
    public static String instr = "3 2\n"
                                 + "1 65\n"
                                 + "5 23\n"
                                 + "2 99\n"
                                 + "10\n"
                                 + "2";
    // REMOVE_END

}