백준 1202 : 보석 도둑 풀이

시간복잡도를 신경써서 풀어야하는 문제이다.

또 보석 가격이 개당 100,000,000 이하이므로 출력하는 총 합은 long 타입이어야 한다.

 

이 문제의 핵심은 가방의 입장에서 넣을 수 있는 최대 가격의 보석을 찾아야한다는 것이다.

그러기 위해, 가방과 보석은 무게순으로 오름차순으로 정렬해 생각해야한다.

 

그럼 더 작은 가방에 넣을 수 있는 무게면 큰 가방도 당연히 그 보석을 넣을 수 있다는 것이다.

따라서 보석은 한번만 우선순위 큐에 넣으면 된다! 단 그 보석이 가능한 가방 차례에!

그럼 가방 차례로 우선순위 큐에서 정렬한 가장 비싼 보석을 꺼낼 수 있다.

 

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

public class Main {
	
	public static long countMax(int[][] jList, int[] bList) {
		long ans = 0;
		Queue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());
		int jindex = 0;
		
		for(int bag : bList) {
			while(jindex < jList.length && jList[jindex][0] <= bag) {
				queue.add(jList[jindex][1]);
				jindex++;
			}
			
			if(!queue.isEmpty()) {
				ans += queue.poll();
			}
		}
		
		return ans;
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int[][] jList = new int[n][2];
		int[] bList = new int[k];
		
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			jList[i][0] = Integer.parseInt(st.nextToken());
			jList[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(jList, (o1, o2) -> {
			if(o2[0] == o1[0]) {
				return o2[1] - o1[1];
			}
			return o1[0] - o2[0];
		});
		
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			bList[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(bList);
		
		System.out.println(countMax(jList, bList));
	}

}