[백준/Java] 1202 보석 도둑

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

문제 요약

각각 무게 $M_i$와 가격 $V_i$를 갖는 보석 N개가 있다.
최대 무게 $C_i$를 담을 수 있는 가방 K개가 있다.
가방에는 최대 1개의 보석만 넣을 수 있을 때, 얻을 수 있는 최대 가격을 구하자.

보석의 개수 N과 가방의 개수 K는 최대 300만이다.
각 보석의 무게와 가격은 최대 100만이다.
가방에 담을 수 있는 무게는 최대 1억이다.

---

문제 접근

먼저 문제의 입력값 범위를 고려하면 전체 시간복잡도를 $O(NlogN)$ 내에 수행해야 시간 내에 문제를 해결할 수 있을 것 같다.
그런데 모든 보석 또는 가방을 한 번은 훑어야 할 것이기 때문에, 이를 훑는 루프 내에서는 $O(logN)$의 시간복잡도를 사용해야 한다.

이러한 시간복잡도를 지킬 수 있는 대표적인 예시로는 우선순위 큐가 있다.
우선순위 큐의 삽입과 삭제 연산은 $O(logN)$에 수행되기 때문에, 이를 잘 활용하면 문제를 해결할 수 있을 것 같다.

문제를 해결하는 접근은 다음과 같다.
먼저 가방의 무게를 오름차순으로 정렬하고, 보석도 무게 오름차순으로 정렬한다.
그리고 해당 무게에 보석이 들어갈 수 있다면, 보석의 가치를 내림차순으로 하는 우선순위 큐에 넣는다.
이를 모든 가방에 대해 수행한다.
마지막으로 우선순위 큐에서 가방의 개수만큼 빼서 가치를 더하면 정답이 된다.

이렇게 문제를 해결할 수 있는 이유는 하나의 가방에 하나의 보석만 들어갈 수 있기 때문이다.
가방의 무게를 오름차순으로 정렬하고 이러한 작업을 수행하기 때문에, 이전 가방에 넣을 수 있는 보석은 이후 가방도 모두 넣을 수 있기 때문에 가능하다.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (정리 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {

    static int N, K;

    static PriorityQueue<int[]> pq;
    static int[] maxWeightsOfBag;
    static int[][] informationOfJewel;

    public static void getInput() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st1 = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st1.nextToken());
        K = Integer.parseInt(st1.nextToken());
        
        informationOfJewel = new int[N][2];
        
        // 보석의 정보 저장
        for (int i = 0; i < N; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	
        	informationOfJewel[i][0] = Integer.parseInt(st.nextToken());
        	informationOfJewel[i][1] = Integer.parseInt(st.nextToken());
        }

        // 가방의 최대 무게 리스트 얻기
        maxWeightsOfBag = new int[K];

        for (int j = 0; j < K; j++) {
            int maxWeight = Integer.parseInt(br.readLine());
            maxWeightsOfBag[j] = maxWeight;
        }
        
        // 우선순위 큐 선언(가치가 높은 것부터)
        pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        // Integer.compare(o1[0], o2[0]) 이런 식으로 하는게 오름차순이라는 것이 직관적이라 더 나을 수 있다.
        
        // 리스트 정렬
        Arrays.sort(maxWeightsOfBag);
        Arrays.sort(informationOfJewel, new Comparator<int[]>(){
        	@Override
        	public int compare(int[] o1, int[] o2) {
        		return Integer.compare(o1[0], o2[0]);
        	}
        });
    }
    
    // 가방에 넣을 수 있는 모든 보석을 기록하고, 가방의 개수만큼만 꺼내서 가치를 얻기
    public static long takeJewel() {
    	int jewelIdx = 0;
    	long value = 0;
    	
    	for (int i = 0; i < K; i++) {
    		// 모두 무게의 오름차순으로 정렬되어, 가방에 보석을 넣을 수 있다면 우선순위 큐에 추가함
    		while (jewelIdx < N && informationOfJewel[jewelIdx][0] <= maxWeightsOfBag[i]) {
    			pq.add(informationOfJewel[jewelIdx]);
    			jewelIdx++;
    		}
    		
    		// 현재 가방에 넣을 수 있는 가장 가치가 높은 것을 꺼냄
    		if (pq.isEmpty()) {
    			continue;
    		}
    		int[] jewel = pq.poll();
    		value += jewel[1];
    	}
    	
    	return value;
    }

    public static void main(String[] args) throws IOException {
        getInput();

        long totalValue = takeJewel();

        System.out.println(totalValue);
    }
}

---

회고

틀렸던 이유 1
재귀를 이용해 방문했던 도로를 제거하는 과정에서, 이미 방문했던 장소를 다시 방문하지 않는 코드를 작성하지 않아 시간 초과가 발생했다.

틀렸던 이유 2
방문 장소를 다시 방문하지 않는 코드를 작성했다. 다만 순서 상 현재 사용한 도로는 제거하고 다음 재귀를 진행하지 않아야 하는데, 사용한 도로를 제거하지 않고 끝내버려서 거의 최단 경로를 잘못 구하게 되었다.