[알고리즘][X] 보석 도둑

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

1202번: 보석 도둑

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static class Jewel {
		int M; // 무게
		int V; // 가격
		
		
		public Jewel() {
			super();
		}


		public Jewel(int m, int v) {
			super();
			M = m;
			V = v;
		}
	}
	public static void main(String[] args) throws Exception {
		// 보석 N, 무게 M, 가격 V, 가방 수 K 가방 최대 무게 C
		// 차원: 보석, 무게, 가방 3차원
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()), K = Integer.parseInt(st.nextToken());
		Jewel[] jewels =new Jewel[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			jewels[i] = new Jewel();
			jewels[i].M = Integer.parseInt(st.nextToken());
			jewels[i].V = Integer.parseInt(st.nextToken());
		}
		
		int[] C = new int[K];
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			C[i] = Integer.parseInt(st.nextToken());
		}
		// 보석을 무게 오름차순으로 정렬
		// 가방을 무게 오름차순으로 정렬
		Arrays.sort(jewels, new Comparator<Jewel>() {

			@Override
			public int compare(Jewel o1, Jewel o2) {
				return o1.M - o2.M;
			}
		});
		Arrays.sort(C);
		
		// 가방과 보석에 각각 포인터를 두고 현재 가방보다 낮은 무게를 가지는 보석을 넣어둠
		// 이때 보석을 넣어두는 장소는 힙으로 가치 내림차순으로 정렬
		
		PriorityQueue<Jewel> pq = new PriorityQueue<>(new Comparator<Jewel>() {

			@Override
			public int compare(Jewel o1, Jewel o2) {
				return o2.V - o1.V;
			}
		});
		
		long result = 0;
		
		int bagIdx = 0;
		int jewelIdx = 0;
		// 가방을 모두 보거나 보석을 모두 보면 일단 종료
		while (bagIdx < K && jewelIdx < N) {
			if (C[bagIdx] >= jewels[jewelIdx].M) {
				pq.add(jewels[jewelIdx]);
				jewelIdx++;
				continue;
			}
			
			// 보석이 있다면 최대 가치 더해줌
			if (!pq.isEmpty()) {				
				Jewel jewel = pq.poll();
				result += jewel.V;
			}
			bagIdx++;
		}
		
		// 가방이 남아있고 보석도 남아있다면 하나가 남지 않을때까지 계속
		while (bagIdx < K && !pq.isEmpty()) {
			Jewel jewel = pq.poll();
			result += jewel.V;
			bagIdx++;
		}
		
		System.out.println(result);
	}
}

나의 풀이

- 보석 하나의 최대 크기가 1억이고 최대 개수가 300,000 이기 때문에 long을 써야 한다. 이것 때문에 틀렸었다.

- dp로 풀려고 하면 시간초과가 난다.

- 따라서 그리디를 활용해야 한다.

- 먼저 무게별로 가방과 보석을 각각 정렬해준다.

- 그리고 가방과 보석에 각각의 현재 위치를 가리키는 포인터를 둔다.

- 현재 가방보다 낮은 무게를 가진 보석을 모두 힙에 넣어준다. 이때 힙은 보석의 가치를 내림차순으로 정렬하는 맥스힙이다.

- 현재 가방보다 낮은 무게를 가진 보석이 없다면 힙에서 최대 가치를 지닌 보석을 빼준다.

- 힙에 있는 보석은 그 다음번째에 있는 가방이 모두 선택할 수 있기 때문에 논리가 성립한다.

- 상대적으로 낮은 최대 무게 가방이 선택의 폭이 좁기 때문에 먼저 선택권을 줘야만 한다. 높은 최대 무게 가방은 낮은 최대 무게 가방이 선택할 수 있는 것 중 어떤 것이라도 선택할 수 있기 때문이다.

- 반대는 성립하지 않는다.