[BaekJoon] 1202 보석 도둑 (Java)

1.  문제 링크

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

2.  문제

요약

• 상덕이가 털 보석점에는 보석이 총 N개 있습니다.
• 각 보석은 무게 $M_i$와 가격 $V_i$를 가지고 있습니다.
• 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 $C_i$입니다.
• 가방에는 최대 한 개의 보석만 넣을 수 있습니다.
• 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 300,000보다 작거나 같은 N과 K가 주어지고 두 번째 줄부터 N개의 줄에는 0보다 크거나 같고 1,000,000보다 작거나 같은 각 보석의 정보 $M_i$와 $V_i$가 주어집니다. 그 다음 줄부터 K개의 줄에는 1보다 크거나 같고 100,000,000보다 작거나 같은 가방에 담을 수 있는 최대 무게 $C_i$가 주어집니다.
  • 모든 숫자는 양의 정수입니다.
• 출력: 첫 번째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력합니다.

3.  소스코드

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

public class Main {
    static int N, K;
    static Jewel[] jewels;
    static int[] bags;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        K = scanner.nextInt();

        jewels = new Jewel[N];
        bags = new int[K];

        for(int jewel = 0; jewel < N; jewel++) {
            int weight = scanner.nextInt(), value = scanner.nextInt();
            jewels[jewel] = new Jewel(weight, value);
        }

        for(int bag = 0; bag < K; bag++)
            bags[bag] = scanner.nextInt();
    }

    static void solution() {
        sort();
        System.out.println(getMaxSum());
    }

    static long getMaxSum() {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        long answer = 0;
        for(int bag = 0, jewel = 0; bag < K; bag++) {
            while(jewel < N && jewels[jewel].weight <= bags[bag]) {
                queue.offer(jewels[jewel++].value);
            }

            if(!queue.isEmpty()) answer += queue.poll();
        }

        return answer;
    }

    static void sort() {
        Arrays.sort(jewels, new Comparator<Jewel>() {
            @Override
            public int compare(Jewel j1, Jewel j2) {
                if(j1.weight != j2.weight) return j1.weight - j2.weight;
                return j2.value - j1.value;
            }
        });

        Arrays.sort(bags);
    }

    static class Jewel {
        int weight, value;
        public Jewel(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}