[백준_1202번] 보석 도둑

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

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)
• 모든 숫자는 양의 정수이다.

 

[코드]

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

class Jewelry {
	int weight, value;
	
	public Jewelry(int weight, int value) {
		this.weight=weight;
		this.value=value;
	}
}

public class BaekJoon_1202 {
	/*
	 * 우선순위 큐를 이용해야 하는 문제 
	 * k개의 가방을 무게가 가벼운 순으로 처리해야 한다.
	 * 보석 또한 무게가 가벼운 순으로 정렬하여 k번째 가방에 들어갈 수 있는 모든 보석을 최대힙에 삽입한다.
	 * 최대힙의 root에는 가방에 들어갈 수 있는 가장 비싼 가격이 들어있기 때문에 root 노드만 poll
	 * 
	 * 가방을 가벼운 순으로 정렬했기 때문에 k번째 가방에 들어갈 수 있는 보석은 k+1번째 가방에도 들어갈 수 있다.
	 * 따라서 이미 최대힙에 들어가있는 보석들도 고려하여 k+1에 들어갈 가방을 구해줘도 된다.
	 */
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		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()); // 가방의 개수
		
		Jewelry[] jewelry=new Jewelry[n];
		
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			
			int w=Integer.parseInt(st.nextToken());
			int v=Integer.parseInt(st.nextToken());
			
			jewelry[i]=new Jewelry(w,v);
		}
		
		// n개의 보석은 무게가 가벼운 순으로 정렬, 무게가 같다면 가격 순으로 정렬
		Arrays.sort(jewelry, new Comparator<Jewelry>() {
			@Override
			public int compare(Jewelry o1, Jewelry o2) {
				// TODO Auto-generated method stub
				if(o1.weight==o2.weight)
					return o1.value-o2.value;
				
				return o1.weight-o2.weight;
			}
		});
		
		int[] bag=new int[k];
		for(int i=0;i<k;i++) 
			bag[i]=Integer.parseInt(br.readLine());
		
		Arrays.sort(bag); // 가방은 무게가 가벼운 순부터 처리
		
		// 현재 가방에 넣을 수 있는 가장 값어치 있는 보석이 들어있는 우선순위 큐(최대 힙)
		PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder()); 
		int index=0; // n개의 보석을 가르키는 포인터
		long total=0;
		
		for(int i=0;i<k;i++) {
			// n개의 보석 중 가방에 들어갈 수 있는 무게의 보석은 큐에 삽입
			while(index<n&&jewelry[index].weight<=bag[i]) {
				pq.add(jewelry[index].value);
				index++; // 포인터 증가
			}
			
			// 큐에 제일 위에있는 노드가 가방에 넣을 수 있는 가장 비싼 보석
			if(!pq.isEmpty())
				total+=pq.poll();
		}
		
		System.out.println(total);
	}

}

 

[고찰]

 이번 문제는 특정 자료구조를 사용하여 해결해야 시간초과 없이 정답처리를 받을 수 있는 문제였다. 여기서 사용해야 하는 자료구조는 우선순위 큐이고 이와 더불어 여러가지 생각해야 하는 조건이 많은 문제였다. 

 우선 보석의 가격과 무게를 저장하는 클래스를 담을 배열을 선언한 뒤 해당 배열을 무게가 가벼운 순으로(무게가 같다면 가격이 비싼 순으로) 정렬해야 한다. 그 이유는 가벼운 가방부터 보석을 담아야 하기 때문이다. k번째 가방에 담을 수 있는 보석은 k번째 가방보다 담을 수 있는 보석의 무게가 큰 k+1번째 가방에도 담을 수 있기 때문에 가벼운 가방 순서대로 보석을 담아준다. 

 우선순위 큐에는 k번째 가방에 담을 수 있는 보석의 무게가 저장되어있는데, 최대힙으로 reverseorder() 해주었으므로 우선순위 큐의 가장 위에는 가격이 제일 비싼 보석이 들어있다. 따라서 k번째 가방에 들어갈 수 있는 모든 보석을 우선순위 큐에 삽입한 뒤 가장 위에있는 보석만 빼 가격의 누적 합을 구해주면 된다. 

 

 이번 문제는 스스로 알고리즘을 생각해내기에는 어려움이 있는 문제였다. 하지만 지금 듣고있는 알고리즘 특강을 진행해주시는 강사님의 설명을 들으니 스스로 구현할 수 있었다. 다음에는 스스로 생각하고 구현해봐야겠다.