[Java] 백준 1202. 보석 도둑

📌 문제 링크 - 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)

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

 

 

 

출력

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

 

 

 

 

힌트 : 두 번째 예제의 경우 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 넣으면 된다.

 

 

---

 

 

풀이

처음에는 단순하게 우선순위큐를 사용하여 보석 가격 기준으로 내림차순, 가방에 담을 수 있는 무게 기준으로 내림차순 해서 제출했었다. 그리고 3%에서 틀렸다..

 

반례를 찾아보니 

9 5
4 5
4 9
4 10
8 55
14 20
9 15
8 55
8 5
11 54
10
5
4
15
20
----
정답 : 183

 

보석 9개, 가방 5개(20, 15, 10, 5, 4)

이러한 반례가 있었고, 내가 짠 로직대로라면 183이 아닌 144가 나왔다. 

 

그림으로 보면 아래와 같다.

틀림 (144)

보석은 가격을 기준으로 내림차순, 가방도 무게를 기준으로 내림차순 후 가방에 담을 수 있는 보석이라면 보석 가격을 더해주는 식으로 코드를 짰었다. 때문에 '55 + 55 + 15 + 10 + 9 = 144'라는 결과가 나온 것이다. 

 

 

하지만 아래처럼 보석을 훔친다면 183이 나온다.

정답 (183)

 

 

 

큰 가방은 작은 가방이 담지 못하는 보석도 담을 수 있으니 가방 오름차순, 보석도 무게를 기준으로 오름차순을 했다. 또 가장 비싼 보석을 훔치기 위해 가격을 기준으로 내림차순 한 임시 주머니를 만들어서 현재 가방이 담을 수 있는 보석들을 임시 주머니에 다 넣어주고, 임시 주머니에서 가장 비싼 보석을 꺼내 가격을 더해주는 식으로 변경하였다.

// 임시 주머니 (보석 가격 기준으로 내림차순)
PriorityQueue<Integer> tmp = new PriorityQueue<>(Collections.reverseOrder());
long sum = 0; // 훔칠 수 있는 보석의 최대 가격 		
int bag;		

while(!bags.isEmpty()) {
    bag = bags.poll(); // 현재 가방 무게

    // 임시 주머니에 현재 가방에 담을 수 있는 보석 다 담아
    while(!jewels.isEmpty() && jewels.peek().M <= bag) {
        tmp.offer(jewels.poll().V);
    }//while

    if(!tmp.isEmpty()) sum += tmp.poll(); // 보석 무게 더해주기
}//while

return sum;

 

 

 

위의 그림처럼 가방4가 담을 수 있는 보석 3개를 임시 주머니에 넣은 후 그중 제일 비싼 보석인 1번 보석을 꺼내 10원을 더해준다. 그 후 남아있는 보석 중(무게 8부터 14)에 가방5가 가질 수 있는 보석은 없으므로 가방5는 임시 주머니에서 가장 비싼 보석인 2번 보석을 꺼내 9원을 더해준다. 가방10은 보석 무게가 8부터 9까지 다 가능하므로 임시 주머니에 담아준 후 임시 주머니에서 가장 비싼 보석인 5번 보석을 꺼내 55를 더해주게 된다. 이렇게 가방20까지 반복해서 최종적으로 183원이 나오게 된다.

 

 

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/1202
public class Main_1202 {
	static PriorityQueue<Jewel> jewels; // 보석
	static PriorityQueue<Integer> bags; // 가방


	public static void main(String[] args) throws Exception {
		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()); // 가방 개수
		
		jewels = new PriorityQueue<>(); // 보석들 (보석 무게 기준으로 오름차순)
		while(N-->0) {
			st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			jewels.offer(new Jewel(M, V));
		}//while
		
		bags = new PriorityQueue<>(); // 가방들(가방 무게 기준으로 오름차순)
		while(K-->0) {
			bags.offer(Integer.parseInt(br.readLine()));
		}//while
		br.close();
		
		long max = getMax();
		System.out.print(max);
	}//main


	private static long getMax() {
		// 임시 주머니 (보석 가격 기준으로 내림차순)
		PriorityQueue<Integer> tmp = new PriorityQueue<>(Collections.reverseOrder());
		long sum = 0; // 훔칠 수 있는 보석의 최대 가격 		
		int bag;		

		while(!bags.isEmpty()) {
			bag = bags.poll(); // 현재 가방 무게
			
			// 임시 주머니에 현재 가방에 담을 수 있는 보석 다 담아
			while(!jewels.isEmpty() && jewels.peek().M <= bag) {
				tmp.offer(jewels.poll().V); // 보석 가격 담기 
			}//while
			
			if(!tmp.isEmpty()) sum += tmp.poll(); // 보석 가격 더해주기
		}//while
		
		return sum;
	}//getMax


	static class Jewel implements Comparable<Jewel> {
		int M; // 보석 무게
		int V; // 보석 가격
		public Jewel(int M, int V) {
			this.M = M;
			this.V = V;
		}
		@Override
		public int compareTo(Jewel j) {
			return this.M - j.M; // 보석 무게 오름차순
		}
	}//Jewel
    
	
}//class