[BOJ] 1202 보석도둑

1202 보석도둑

난이도 : 골드 2
유형 : 그리디 알고리즘, 우선순위 큐

https://www.acmicpc.net/problem/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)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

풀이

처음에 보석의 개수와 가방의 개수를 고려하지 않고 풀었다가 시간초과가 났다.
가방에는 최대 한 개의 보석을 넣을 수 있기 때문에, 가방에 넣을 수 있는 보석들 중 가장 가격이 많이 나가는 보석을 넣어야 한다.
1. 각 보석의 정보를 2차원 배열에 저장
2. 보석 정보의 배열을 보석의 무게를 기준으로 오름차순 정렬, 무게가 같은 경우에는 가격을 기준으로 내림차순 정렬
3. 가방에 최대 넣을 수 있는 무게 정보를 1차원 배열에 저장
4. 무게를 기준으로 가방 배열 오름차순 정렬
여기서부터 중요한 아이디어였다.
5. 보석의 가격을 내림차순으로 정렬해줄 우선순위 큐를 선언
6. 현재 가방이 담을 수 있는 최대 무게보다 작거나 같은 무게를 가진 보석들을 우선순위 큐에 담아준다.
7. 우선순위 큐의 제일 첫 번째 값(가장 가격이 비싼 보석)을 꺼내어 더해준다.
8. 6.7번을 가방의 개수만큼 반복

코드

import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * BOJ_1202_G2_보석도둑
 * @author mingggkeee
 * 우선순위 큐, 그리디 알고리즘
 */

public class BOJ_1202 {
	
	static int N, K;
	static int[][] info;
	static boolean[] isVisited;
	static int[] bags;
	
	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());	// 가방의 개수
		
		info = new int[N][2];
		isVisited = new boolean[N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			info[i][0] = Integer.parseInt(st.nextToken());	// 보석의 무게
			info[i][1] = Integer.parseInt(st.nextToken());	// 보석의 가격
		}
		
		// 무게 오름차순 정렬하는데 무게가 같을 경우에는 가격을 내림차순으로 정렬
		Arrays.sort(info, new Comparator<int []> () {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o2[0]==o1[0]) {
					return o2[1]-o1[1];
				}
				return o1[0]-o2[0];
			}
			
		});
		
		bags = new int[K];
		
		for(int i=0; i<K; i++) {
			bags[i] = Integer.parseInt(br.readLine());
		}
		
		// 가방 오름차순
		Arrays.sort(bags);
		
		long result = 0;
		
		// 가격이 내림차순 정렬하기 위해
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		
		for(int i=0, j=0; i<K; i++) {
			
			while(j<N && info[j][0] <= bags[i]) {
				pq.offer(info[j++][1]);
			}
			
			if(!pq.isEmpty()) {
				result += pq.poll();
			}
			
		}
		
		System.out.println(result);

		
	}

}