알고리즘 풀이 - 백준 1202(보석 도둑, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N개의 보석 중 가방에 넣을 수 있는 최대 K개의 보석을 훔치고자 한다. 각 가방의 최대 담을 수 있는 무게는 C라고 할 때, 각 가방에 1개씩 넣어 최대로 훔칠 수 있는 보석의 가격을 구하는 문제

 

 

2. 풀이

 

보석이 최대 N개인데 N은 최대 1백만, 가방은 최대 K인데 30만개 이다. 각 가방마다 보석을 넣으려면 단순 2중 반복문을 수행하여 진행하게 되는 경우, 무조건 시간 초과가 발생한다.

 

따라서, 이 문제는 시간 초과가 발생하지 않도록 우선순위 큐를 이용하여 문제를 풀어야 한다. 우선순위 큐 포스팅은 여기를 참조

 

 

이 문제는 단순하게 각 가방에 들어갈 수 있는 모든 보석들 중, 가격이 가장 높은 보석을 하나씩만 넣어 그 가치를 모두 더하면 해결할 수 있다.

그런데, 주의할 점은 담을 수 있는 무게가 작은 가방 부터 먼저 채워야 한다는 것이다.

 

예를 들어, 아래와 같은 예시의 경우를 살펴보자.

 

 

위와 같은 상황일 때, 크기가 큰 10짜리 가방에 가장 가치가 높은 99짜리를 넣고 나면 어떻게 될까?

그러면 아래와 같이 남게 된다!

 

 

이미 훔친 보석과 사용한 가방을 제외하면, 위와 같이 남는데 더 이상 가방에 보석을 넣어서 훔칠 수가 없다. 현재 훔친 보석의 총 가격은 99가 된다.

 

그런데 반대로, 담을 수 있는 무게가 더 작은 2짜리 가방에 99 가격의 보석을 넣으면 10짜리 가방에는 추가적으로 65 가격의 보석을 더 넣을 수 있다!

 

 

그래서 총 훔친 보석 가격의 최대값은 164가 된다.

 

 

즉, 가방은 작은 것을 우선하여, 보석은 담을 수 있는 모든 보석 중 가치가 높은 것을 찾아야 하므로 무게를 기준으로 오름차순 및 가격을 기준으로 오름차순된 자료구조로 저장해야 한다.

이 문제는 N, K의 최대 범위가 상당히 크기 때문에, 정렬 시에 단순 배열, 연결리스트 등을 사용하면 시간 내에 문제를 해결할 수 없다.

 

그래서 O(logn) 수준으로 정렬하여 문제를 해결할 수 있는 우선순위 큐를 이용하여 해결한다.

 

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n, k;
    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());

        // 보석 정보를 입력 받고, 정렬 기준에 맞게 정렬 수행
        PriorityQueue<Jew> jpq = new PriorityQueue<>();
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            jpq.offer(new Jew(m, v));
        }

        // 가방 정보를 입력 받고, 가벼운 가방을 우선하여 오름차순 정렬 수행
        PriorityQueue<Integer> bpq = new PriorityQueue<>();
        for(int i=0; i < k; i++){
            bpq.offer(Integer.parseInt(br.readLine()));
        }

        // 현재 가방에 넣을 수 있는 무게인 보석들을 모은 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        long ans = 0; // 전체 보석의 무게
        // 각 가방에 보석을 넣는 경우를 검사
        while(!bpq.isEmpty()){
            int size = bpq.poll(); // 현재 가방의 무게
            
            // 현재 가방에 넣을 수 있는 보석 중 가장 가치가 높은 것을 찾는다. 
            while(!jpq.isEmpty()){
                // 현재 체크 대상 보석
                Jew j = jpq.peek();
                
                // 현재 가방보다 무거운 경우, 더 이상 체크할 필요가 없다.
                if(j.w > size){
                    break;
                    
                // 넣을 수 있는 보석들은 -1을 곱하여 우선순위 큐에 오름차순 순으로 정렬해 저장
                } else {
                    pq.offer(jpq.poll().v * -1);
                }
            }
            
            // 현재 훔칠 수 있는 보석 중 가장 가치가 높은 것을 1개 뽑아 정답에 추가
            if(!pq.isEmpty()){
                ans += pq.poll();
            }
        }
        
        // 기존에 -1을 곱해서 더해왔기 때문에 마지막에 -1을 곱해서 진짜 정답을 구한다.
        System.out.println(ans*-1);
        br.close();
    }
}

class Jew implements Comparable<Jew>{
    int w;
    int v;
    public Jew(int w, int v){
        this.w = w;
        this.v = v;
    }

    // 보석은 가치가 큰 것을 우선하여 내림차순으로 정렬할 수 있도록 기준을 지정
    @Override
    public int compareTo(Jew o) {
        return this.w - o.w;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.