쌉쌀한 무화과의 개발로그

[문제]

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

상덕이가 털 보석점에는 보석이 총 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)

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

[출력]

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

[예제]

[힌트]

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

>문제 풀이

주어진 보석들의 무게와 값어치를 Gem(weight, price)를 이용하여 Gem[] gem에 저장해줍니다.

우리는 주어진 가방안에 담을 수 있는 무게의 보석들 중에 가장 높은 값어치의 보석을 담아야 합니다.

​

보석: 처음에는 무게를 기준으로 정렬을 해야하고, 가방에 담을 수 있는 보석들을 대상으로 다시 값이 가장 높은 보석을 구해줍니다.

가방: 무게 기준으로 오름차순 정렬을 해주고 보석을 담아야합니다. 그래야 가방이 담을 수 있는 무게보다 더 적은 무게의 보석들을 고려할 수 있습니다.

ex) 가방= 3, 10 보석: (3, 40) (5, 30) (7, 15) (10, 20) =>이럴 경우 첫번째 가방에 (3, 40)을 담고, 두번째 가방에 (5, 30)을 담아야 합니다.

​

1. 보석들을 무게 기준으로 오름차순 정렬을 합니다.

(2차원 배열이라 weight과 price 중에 기준을 정해줘야합니다.)

​

2. 가방을 무게기준으로 오름차순 정렬을 해줍니다.

​

3. Priority Queue를 선언해줍니다. 이 때 기준을 정해줘야하는데, 값을 기준으로 할 것입니다.

포인터 gIndex=0;

​

4. 연산

for(i: 가방) {
     while(포인터를 옮겨주며 N보다 작고, gem[gIndex]가 가방의 무게 i보다 작은) {
          조건의 보석들을 pq에 넣어줍니다.
     }
     pq가 비어있지 않다면 result+=pq.poll().price;
}

>전체 코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scan= new Scanner(System.in);
		
		int N= scan.nextInt();
		int K= scan.nextInt();
		Gem[] gem= new Gem[N];
		int[] bags= new int[K];
		
		int w, p;
		for(int i=0; i<N; i++) {
			w= scan.nextInt();
			p= scan.nextInt();
			gem[i]= new Gem(w, p);
		}
		
		for(int i=0; i<K; i++) {
			bags[i]= scan.nextInt();
		}
		
		// 가방 오름차순 정렬
		Arrays.sort(bags);
		// 보석 무게순 정렬(ascending)
		Arrays.sort(gem, (g1, g2)-> Integer.compare(g1.weight, g2.weight));
		// 보석 높은 값 기준 힙
		PriorityQueue<Gem> pq= new PriorityQueue<>((g1, g2)-> Integer.compare(g2.price, g1.price));
		
		int gIndex=0;
		long result=0;
		//1. 남은 가방 중 제일 작은 가방을 선택
		for(int i=0; i<bags.length; i++) {
			//2. 선택된 가방에 넣을 수 있는 남은 보석 중 가장 비싼 보석을 선택(1가방, 1보석)
			while(gIndex<N && gem[gIndex].weight<=bags[i]) {
				pq.add(gem[gIndex++]);
			}
			if(!pq.isEmpty()) result+=pq.poll().price;
		}
		
		System.out.println(result);
		
	}//main
	
	static class Gem {
		int weight;
		int price;
		
		public Gem(int weight, int price) {
			this.weight= weight;
			this.price= price;
		}
	}
}

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