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

접근 방식

무게와 가격을 가진 보석.. 이걸 담는 가방.. 보자마자 DP문제인가? 싶었지만 아니었다.
가방에는 한 개씩 담을 수 있고 가장 비싸게 훔쳐올때의 가격을 구하는 문제다. 즉 그리디하게 접근해야한다.

사실 이 문제는 다른 사람의 풀이를 보고 힌트를 얻었는데
정리하자면, 제일 작은 가방부터 이 가방이 담을 수 있는 보석들 중 가장 가격이 큰 보석을 담으면 된다.

1. 보석의 정보를 담는 배열과, 가방 정보를 담는 배열을 무게에따라 오름차순으로 정렬해준다.

2. 가방을 하나씩 탐색하면서 가방이 담을 수 있는 무게까지의 보석들의 가격을 우선 순위 큐에 넣어준다. 우선순위 큐는 내림차순 정렬이여야 한다.

3. 현재 우선순위 큐에 몇 번째 보석까지 들어가있는지 저장하는 변수 지정

3번 과정이 제일 핵심이다. 처음에 짠 코드는 가방 탐색이 진행될때마다 우선순위 큐에 보석들을 다시 넣어줬었다. 당연히 시간초과가 떴다.
우선순위 큐에서 생기는 불필요한 반복 과정을 줄여줘야 하는데, 현재 몇 번째 보석까지 들어왔는지를 알려주는 변수를 통해 시간을 단축할 수 있다.

예를 들어 가방이 담을 수 있는 무게가 5라고 한다면, 무게가 5까지인 보석들의 가격이 우선 순위 큐에 담긴다. 5바로다음으로 무게가 큰 보석의 번째를 저장하는 변수(end)가 있다. 만약 다음 가방의 담을 수 있는 무게가 10이라면 end부터 무게가 10인 보석까지들을 우선순위에 담아주고 거기서 제일 큰 가격을 고르면 되는것이다. 이 방법을 통해 시간을 단축시켰고 통과 할 수 있었다. 솔직히 어려운 문제였다.

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

public class Main_1202_보석도둑2 {
	static class Jew {
		int M, V;

		public Jew(int M, int V) {
			this.M = M;
			this.V = V;
		}
	}
	public static void main(String[] args) throws IOException {
		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());

		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		long sum = 0;
		Jew[] jewList = new Jew[N]; //보석 정보를 담는 배열
		int[] bagList = new int[K]; //가방 정보를 담는 배열

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			jewList[i] = new Jew(M, V);
		}
		for (int i = 0; i < K; i++) {
			int C = Integer.parseInt(br.readLine());
			bagList[i] = C;
		}

		Arrays.sort(jewList, new Comparator<Jew>() {
			@Override
			public int compare(Jew o1, Jew o2) {
				return o1.M - o2.M;
			}
		}); //보석의 무게를 기준으로 오름차순 정렬
		Arrays.sort(bagList); //가방도 오름차순 정렬

		int end = 0;
		for (int i = 0; i < K; i++) {
        		//현재 가방의 무게보다 작거나 같은 보석들의 가격을 우선순위 큐에 넣는다.
			while (end < N && jewList[end].M <= bagList[i])
				pq.offer(jewList[end++].V);
                
			//우선순위 큐가 빌 상황이 생길 수 있다. 이것 또한 중요
			if (!pq.isEmpty())
				sum += pq.poll();
		}
		System.out.println(sum);
	}
}