[Algorithm] 💎백준 1202 보석도둑

0. 문제

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

상덕이가 털 보석점에는 보석이 총 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. 아이디어

💡 무게값으로 오름차순한 후, 무게가 같다면 value기준으로 내림차순 함
💡 가방을 오름차순 정렬함
💡 가방보다 작은 무게를 가진 보석들을 모두 우선순위 큐에 넣음
💡 가방 하나에 한 개 보석이 들어가기 때문에 우선순위 큐에 넣은 것 중에 가방 개수만큼 보석을 꺼내서 더함

2. 핵심 풀이

1. 무게값으로 오름차순한 후, 무게가 같다면 value기준으로 내림차순 함

Arrays.sort(jewelry, new Comparator<int[]>() {
	@Override
	public int compare(int o1[], int o2[]) {
		if(o1[0] == o2[0]) return o2[1] - o1[1];
		return o1[0] - o2[0];
	}
});

1. 가방을 오름차순 정렬함

Arrays.sort(backpack);

1. 가방보다 작은 무게를 가진 보석들을 모두 우선순위 큐에 넣음

for(int i=0; i<k; i++) {
	while(idx < n && jewelry[idx][0] <= backpack[i]) {
		pq.add((-1)*jewelry[idx][1]);
		idx++;
	}
...
}

1. 가방 하나에 한 개 보석이 들어가기 때문에 우선순위 큐에 넣은 것 중에 가방 개수만큼 보석을 꺼내서 더함

for(int i=0; i<k; i++) {
	...
	if(!pq.isEmpty()) {
		cnt += Math.abs(pq.poll());
	}
}

3. 코드

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

public class BOJ_1202 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] s = br.readLine().split(" ");
		
		int n = Integer.parseInt(s[0]);
		int k = Integer.parseInt(s[1]);
		
		int[][] jewelry = new int[n][2];
		int[] backpack = new int[k];
		
		for(int i=0; i<n; i++) {
			s = br.readLine().split(" ");
			jewelry[i][0] = Integer.parseInt(s[0]);
			jewelry[i][1] = Integer.parseInt(s[1]);
		}
		
		for(int i=0; i<k; i++) {
			backpack[i] = Integer.parseInt(br.readLine().trim());
		}
		
		Arrays.sort(jewelry, new Comparator<int[]>() {
			@Override
			public int compare(int o1[], int o2[]) {
				if(o1[0] == o2[0]) return o2[1] - o1[1];
				return o1[0] - o2[0];
			}
		});
		
		Arrays.sort(backpack);
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		long cnt = 0;
		int idx = 0;
		
		for(int i=0; i<k; i++) {
			while(idx < n && jewelry[idx][0] <= backpack[i]) {
				pq.add((-1)*jewelry[idx][1]);
				idx++;
			}
			
			if(!pq.isEmpty()) {
				cnt += Math.abs(pq.poll());
			}
		}
		
		System.out.println(cnt);
	}

}

4. 결과

성공✨