[알고리즘] 백준 1202 보석도둑

Halo·2025년 5월 12일

greedy 문제풀이 알고리즘

Algorithm

목록 보기

42/85

🔍 Problem

1202 보석 도둑

📃 Input&Output

🌁 문제 배경

가. 접근 방법
1) 가방에 물건들을 효율적으로 "어떻게" 넣어야 보석 가격 합의 최댓값을 구할 수 있을까? 만약 내가 보석을 훔친다면, 가벼운 무게부터 훔칠 것이다. 왜냐하면 가벼운 무게는 나중에 널찍한 가방(담을 수 있는 공간이 큰)에도 담을 수 있기 때문이다. 하지만 반대로 무거운 물건은 나중에 담으면 담기 어려워지는 상황이 생길 것이다.

위와 같은 상황을 고려해 필자는 가방 사이즈를 작은 순으로 나열하고 해당 가방에 물건들을 넣을 생각이다. 필자는 여기서 한번 더 생각한다. "작은 가방을 선택했으니 낮은 무게부터 골라야 하지 않겠냐고".

이 문제는 가방에 담을 수 있는 물건의 목록 들을 구하는데, 작은 것부터 시작하자는 것이다.

2) 따라서 작은 가방부터 넣을 물건들을 추린 뒤, 그 중에서 가치가 높은 물건을 선택하면 될것이고, 주의할 점은 추리는 공간을 모든 가방이 공유한다는 것이다.

이 전에 추려놨던 물건들은 다음 가방에서도 "무조건" 가져갈 수 있기 때문이다. 왜냐하면 가방 용량 순으로 내침차순 정렬했기에, 이전의 가방보다 현재의 가방의 용량이 무조건 높을 것이기 때문이다.

나. 사용할 알고리즘 및 자료구조 선택
1) 그리디
각 가방에 넣는 보석이 현재시점에서 가장 높은 가치를 가지고 있는 것이기 때문이다.

2) 우선순위 큐
가장 높은 가치를 가진 보석을 선택할 때, 힙으로 정렬된 자료구조를 사용하면 빠르다. 그리고 입력할 때
바로 정렬된다.

📒 해결 과정

가. 물건 정보 2차원 배열을 무게를 기준으로 오름차순 정렬

나. 가방 무게 정보 배열을 오름차순 정렬

다. 가방 정보 배열을 순회해서 넣을 수 있는 무게를 큐에 넣고

라. 다 넣었으면, 가장 높은 가치 Poll하여 결과값에 더함.
참고로 우선순위 큐를 아래와 같이 내림차순으로 설정하여야 한다.

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

❗ Trouble shooting

가. NullPtr 에러

res값 우선순위 큐에서 poll해서 갱신할 때, empty check안해서 생긴 문제. 따라서 다음과 같이 수정
if (!pq.isEmpty()) {
	res += pq.poll();
	}

💻 Code

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

public class P1202 {
    public static void main(String args[]) throws IOException {

        // N : 총 보석 개수
        // K : 상덕이의 가방 개수
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] jwe = new int[N][2];
        int[] bag = new int[K];
        long res = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jwe[i][0] = Integer.parseInt(st.nextToken());
            jwe[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(jwe, (a, b) -> a[0] - b[0]);

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

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        int j = 0;
        for (int i = 0; i < K; i++) {
            while (j < N && jwe[j][0] <= bag[i]) {
                pq.add(jwe[j][1]);
                j++;
            }
            if (!pq.isEmpty()) {
                res += pq.poll();

            }
        }

        bw.write(res + "\n");
        bw.flush();
        bw.close();
    }
}

🎸 기타

가. Arrays.sort의 Big O
$nlogn$ 이다.

나. Buffer로 IO 처리

Input
1 2

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

bw.write(st.nextToken() + "\n");
bw.write(st.nextToken());
bw.flush();
bw.close();

>>
1
2