[JAVA][백준] 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 1

5 10

100 100

11

예제 출력 1

10

예제 입력 2

3 2

1 65

5 23

2 99

10

2

예제 출력 2 

164

접근방법

해당 문제의 시간제한은 1초이며, 경우의수( N)은 30,000까지로 시간복잡도 O(NlogN) 까지 가능할거라고 생각한다.

 

보석 가격의 합이 최대일때는 비싼 보석을 많이 담는것이다. 하지만 이 문제에서는 조건을 하나 더 있다.

보석을 담는 가방에 무게  제한이 있다는 점이다. 이 제한 조건이 있으므로 해서 비싼 순 보다는 가방에 모두 담기 위해서 가방에 적합한 무게 범위 안에서 최대값을 찾는것이 좋다고 생각한다. (그 반대로 해도 무관하기는 하다)

정리해보자면 보석의 무게순으로 정렬하고 주어진 가방의 최대 무게와 비교하여 해당 가방에 담을수 있는 보석들 중 최고 가격을 찾는다. 순서로 정리를 해보면 아래와 같다.

 

1) 보석의 무게순으로 정렬한다.

-> 무게가 같은 경우에는 가격순으로 정렬한다.

 

2) 가방도 무게순으로 정렬해준다.

 

3) 가방 개수 만큼 반복문을 실행하면서 해당 가방에 담을 수 있는 보석들을 담고 그 중 최고가를 찾는다.

 

코드

package Greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

class jewelry{
	int weight;
	int price;
	
	public jewelry(int weight, int price) {
		super();
		this.weight = weight;
		this.price = price;
	}
}

public class BJ_1202 {
	public static void main(String[] args) throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 String[] nk = br.readLine().split(" ");
		 int N = Integer.parseInt(nk[0]);
		 int K = Integer.parseInt(nk[1]);
		 List<jewelry> list = new ArrayList<jewelry>();
		 int[] C = new int[K];
		 
		 for(int i =0;i<N;i++) {
			 String[] mv = br.readLine().split(" ");
			 list.add(new jewelry(Integer.parseInt(mv[0]), Integer.parseInt(mv[1])));
		 }
		 
		 //최대무게 입력
		 for(int i=0; i<K;i++) {
			 C[i] = Integer.parseInt(br.readLine());
		 }
		 
		 Arrays.sort(C);
		 
		 
		 Collections.sort(list, new Comparator<jewelry>() {
			@Override
			public int compare(jewelry o1, jewelry o2) {
				if(o1.weight==o2.weight) return o2.price-o1.price;
				return o1.weight-o2.weight;
			}
		});
        //무게를 정렬하기 위한 그릇
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(Comparator.reverseOrder());
		
		long result = 0;
		
		for(int i=0,j=0;i<K;i++) {
			while(j<N&&list.get(j).weight<=C[i]) {
				q.offer(list.get(j++).price);
			}
			//q의 맨앞에 있는 수는 해당 가방이 담을수있는 최고가의 보석이다.
			if(!q.isEmpty()) {
				result+=q.poll();
			}
		}
		System.out.println(result);
		 
	}
}