백준 1202 보석 도둑 java

그리디 알고리즘

전수민

Nov 23, 2025

TABLE OF CONTENTS

1. 문제에 대하여 📦

2. 코드가 나오기까지 🛠️

(1) 보석, 가방 둘 다 무게 오름차순으로 문제를 푸는 이유

1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/source/84012751

보석은 무게와 가격이 주어지고, 가방은 무게가 주어진다. 가방에는 자신의 무게보다 작은 보석만 담을 수 있으며, 한 번에 하나의 보석밖에 담지 못한다. 일련의 보석과 일련의 가방이 있을 때, 가방에 담은 보석의 최대 가격은 얼마인가?

2. 코드가 나오기까지 🛠️

KEY WORD: 그리디 알고리즘

푸는 방법은 다음과 같다.

가방은 무게 오름차순으로 정렬, 보석은 무게 오름차순, 무게 동등 시, 가격 내림차순 정렬

보석을 담을 가방을 무게가 가장 낮은 것부터 집는다.

해당 가방에 담을 수 있는 (보석 무게 < 가방 무게)인 모든 보석을 후보군으로 보낸다.
(후보군은 가격 내림차순 정렬)

후보군에서 가장 가치가 큰 것을 집는다.

가방을 모두 채울 떄까지 위의 과정 반복

이렇게 있다고 쳤을 때, 제일 작은 가방인 2용량 가방부터 집는다. 2보다 무게가 작은 보석은(1,64)와(2,99)이다. 이 둘을 후보군에 넣는다. 후보군은 가격 내림차순임으로 (2,99)가 선두로 올 것이다.
이 중 (2,99)를 가방에 넣는다.

다음 가방은 용량이 6이다. 이보다 작은 남아있는 보석들을 모두 후보지에 넣는다.

이 중 제일 큰(1,64)를 넣는다.

10에 대해서도 같은 과정을 반복하면 모든 가방에 최대치를 넣을 수 있다.

(1) 보석, 가방 둘 다 무게 오름차순으로 문제를 푸는 이유

후순위 계산인 가방에 가능한 한 선택지를 많이 열어주기 위해서 이다.

가방의 무게가 클수록 선택지가 넓고, 작을수록 좁은 것을 볼 수 있다. 이는 반대로 선택지가 좁은 가방에 최대값을 먼저 고려하면, 비교적 선택지가 넓은 가방에서는 담지 않아도 되는 후보군을 추릴 수 있어, 최대값 산정이 더 쉽다.

또한 무게 내림차순 해서 구하면, 최대 가치를 담지 못하고, 가치 내림차순해서 구하면, 무게가 작은 가방에 담을 수 있었던 보석을 큰 데 담아서 무게가 작은 가방을 활용하지 못하는 경우의 수도 생긴다.

(1) 시간복잡도 분석 ⏳

보석을 모두 우선순위 큐에 넣는다. -> O(N x logN)

보석을 한 번 돌며 후보지에 넣는다. -> O(N)

새로운 값을 후보지에 넣을 때마다 재정렬한다. -> O(logN)

위의 과정에서 1번 따로, 2,3번 같이 일어남. 따라서 최악의 시간복잡도는 O(N x logN) 이다.

3. 코드 🌐

(1) SUDO CODE 💬


// 위에 적어서 생략

(2) JAVA CODE ☕


import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static class Jewel {
        int w;
        int v;
        public Jewel (int w, int v){
            this.w = w;
            this.v = v;
        }    }    static int N, K;
    static int [] bag;
    static PriorityQueue<Jewel> pq = new PriorityQueue<>((a,b) -> {
        if(a.w == b.w) return b.v - a.v;
        return a.w - b.w;
    });    public static void main(String[] args) 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());
        bag = new int [K];
        for(int i = 0; i< N; i++){
            st = new StringTokenizer(br.readLine());
            pq.add(new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }        for(int i = 0; i < K; i++){
            bag[i] = Integer.parseInt(br.readLine());
        }        Arrays.sort(bag);

        long acc = 0;
        PriorityQueue<Jewel> candidate = new PriorityQueue<>((a,b) -> (b.v - a.v));
        for(int i = 0; i < K; i++){
            int now_backpack = bag[i];
            while (!pq.isEmpty() && pq.peek().w <= now_backpack){
                candidate.add(pq.poll());
            }            if(!candidate.isEmpty()) acc += candidate.poll().v;
        }        System.out.printf("%d", acc);
    } }