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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1202번: 보석 도둑

---

2. 내가 푼 방법

보석의 최대 가격을 구해야 하므로 그리디 알고리즘을 이용해야 한다.

 

가방이 들 수 있는 무게와 보석의 무게를 오름차순으로 정렬한 후 코드를 작성했다.

따라서 현재 가방이 들 수 있는 무게까지 보석의 가격을 우선순위 큐에 넣을 수 있고, 보석의 가격을 바로 뽑아내 더해준다.

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1202.java

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

class Main {
    static int N;
    static int K;
    static int[][] jewelry;
    static int[] weight;
    static long result;

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

    public static void solution() {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);

        int k = 0;
        for (int i = 0; i < K; i++) {
            for (int j = k; j < N; j++, k++) {
                if (jewelry[j][0] > weight[i]) break;
                queue.add(jewelry[j][1]);
            }

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

    public static class Tuple implements Comparable<Tuple> {
        int bag;
        int value;

        public Tuple(int bag, int value) {
            this.bag = bag;
            this.value = value;
        }

        @Override
        public int compareTo(Tuple t) {
            return t.value - this.value;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        jewelry = new int[N][2];
        weight = new int[K];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewelry[i][0] = Integer.parseInt(st.nextToken());
            jewelry[i][1] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < K; i++) {
            weight[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(jewelry, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) return b[1] - a[1];
                return a[0] - b[0];
            }
        });
        Arrays.sort(weight);

        br.close();
    }
}

---

4. 결과 및 회고

쉽게 푼 문제였지만, 결과 값의 자료형을 long형이었다는 부분에서 삽질을 했다. 범위 값 잘 확인해야지.