백준 1202 - 보석 도둑

Java

1202 번 - 보석 도둑

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)
다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)
모든 숫자는 양의 정수이다.

접근 방법

문제의 조건을 보면, N과 K가 최대 300000이다.
즉 O(N * K)이면 시간초과가 날 가능성이 크며, 보석의 정보가 하나당 최대 1,000,000이므로 결과는 long이 되어야 한다.

문제의 핵심은, 한번 확인한 보석은 다시 돌아보지 않는 다는 것이다.

1. 보석의 정보를 담은 클래스를 만들고, 보석의 무게순, 가방의 무게순으로 오름차순 정렬을 한다.
2. 이제 가방의 무게가 작은 순서로 하나씩 확인한다.
3. 해당 가방보다 무게가 작은 보석들은 그 가방에 들어갈 수 있으므로, 들어갈 수 있는(가방보다 무게가 작은) 보석들을 Priority Queue에 넣는다.
4. 해당 PQ는 보석의 가치 순으로 정렬되어 있으므로, 들어가는 보석의 가치가 높은 순으로 들어있다.
5. 현재 가방에 넣을 수 있는 보석을 다 넣었으면, 현재까지 확인한 보석의 인덱스를 남겨두고, 가장 가치가 큰 보석을 가방에 넣는다(poll())
6. 다음 가방을 확인하되, 현재까지 확인한 보석의 인덱스가 남아있으므로, 그 보석부터 다시 가방에 넣을 수 있는지 확인한다.
7. 만약 현재 가방의 크기보다 다음 보석의 무게가 더 커서 pq에 하나에 넣지 못했더라도, 이전에 넣을 보석 중에 가장 가치가 큰 보석을 넣는다.

위 방식을 이용하면, 매 가방마다 보석들을 확인하지 않고 보석을 한번씩만 확인하므로 시간 복잡도는 O(N + K)가 된다.
이는 O(n) 이므로 충분히 시간 내에 계산 가능하다.

코드

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

public class Main {
	static int n, k;
	static long result;
	static List<Jewel> jem;
	static int[] bag;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	
    	jem = new ArrayList<>();
    	
    	// 무게 M, 가격 V
    	int m,v;
    	for(int i = 1; i <= n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		m = stoi(stk.nextToken()); 	// 무게 
    		v = stoi(stk.nextToken());	// 가격
    		jem.add(new Jewel(m,v));
    	}
    	
    	// 가방 들
    	bag = new int[k];
    	for(int i = 0; i < k; i++) {
    		bag[i] = stoi(br.readLine());
    	}
		// 보석 무게를 기준으로 오름차순으로 정렬
    	Collections.sort(jem, new Comparator<Jewel>() {
			@Override
			public int compare(Jewel o1, Jewel o2) {
				return Integer.compare(o1.m, o2.m);
			}
    		
		});
    	Arrays.sort(bag);
    	// 보석의 가격를 기준으로 내림차순으로 정렬 : root는 항상 최고의 가치를 가진 보석이다
    	PriorityQueue<Jewel> pq = new PriorityQueue<>(new Comparator<Jewel>() {
			@Override
			public int compare(Jewel o1, Jewel o2) {
				return -Integer.compare(o1.v, o2.v);
			}
		});
    	
    	int idx = 0;
		// 가방을 하나씩 탐색
    	for(int i = 0; i < k; i++) {
			// 해당 가방의 무게보다 작은 보석들을 가방에 다 넣는다.  
    		while(true) {
    			if(jem.size() == idx || bag[i] < jem.get(idx).m) {
    				break;
    			}
    			pq.add(jem.get(idx));
    			idx++;
    		}
			// 현재 담을 수 있는 보석 중에 가장 가치가 큰 보석을 가방에 넣는다.
    		if(!pq.isEmpty())
    			result += pq.poll().v;
    	}
    	
    	System.out.println(result);
    	br.close();
	}

	static class Jewel {
		int m,v;

		public Jewel(int m, int v) {
			super();
			this.m = m;
			this.v = v;
		}
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

Knap Sack 문제인 줄 알고, 생각해보다가, 애초에 가능 할 수 없는 문제였다.
최소 O(n^2)이니, 풀 수 없는 문제였으니 미리 알아 챌 필요가 있었다.

개선할 점

없습니다.