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

05 Aug 2023 in Algorithm on 자료 구조

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

풀이

가방의 용량이 정해져있고, 가방에는 보석을 한개씩 넣을 수 있다.

즉, 가방을 오름차순으로 보면서 넣을 수 있는 보석 중 가치가 가장 큰것을 넣으면서 진행한다.

가방을 오름차순으로 정렬하고

가방의 사이즈보다 보석의 무게가 작다면 우선순위큐에 넣고

우선순위큐에서 위의 것을 빼면 되도록 구현했다.

---

메모리: 115988KB

시간: 1888ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static class Node {
        int m;
        int v;

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

    }

    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 M = Integer.parseInt(st.nextToken());

        Node[] gem = new Node[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            gem[i] = new Node(m, v);
        }

        Arrays.sort(gem, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.m == o2.m) {
                    return Integer.compare(o2.v, o1.v);
                } else {
                    return Integer.compare(o1.m, o2.m);
                }
            }

        });

        int[] bag = new int[M];
        for (int i = 0; i < M; i++) {
            bag[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(bag);

        long ans = 0;
        int idx = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0; i < M; i++) {
            int size = bag[i];
            while (idx < N && gem[idx].m <= size) {
                pq.add(gem[idx++].v);
            }

            if (!pq.isEmpty()) {
                ans += pq.poll();
            }
        }

        System.out.println(ans);
    }

}