백준 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)

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

출력

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

제한

• 시간 제한 : 1초
• 메모리 제한 : 256MB

---

문제 풀이 과정

그리디 알고리즘을 사용해서 해결 가능하다.

가방에는 보석 1개가 최대이므로, 가장 비싼 보석을 넣는게 좋다.

모든 가방 + 모든 보석을 검사하면 되지만 시간 초과가 난다.

1. 보석 무게 오름차순 정렬, 무게 같을시 가격 내림차순 정렬
2. 가방 오름차순 정렬
3. 가격 순서대로 내림차순 정렬하는 우선순위큐 생성
4. 가방이 담을 수 있는 뭭보다 작거나 같은 무게를 가진 보석을 우선순위 큐에 담는다.
5. 우선순위큐에 있는 젤 첫번째 값(가장 비싼 보석)을 더해준다.

---

정답 코드

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

class Main1202 {

	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());

		List<Jewel> jewels = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int weight = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			jewels.add(new Jewel(weight, value));
		}

		jewels.sort((o1, o2) -> {
			if (o1.weight == o2.weight) {
				return o2.value - o1.value;
			}
			return o1.weight - o2.weight;
		});

		List<Integer> bags = new ArrayList<>();
		for (int i = 0; i < K; i++) {
			int volume = Integer.parseInt(br.readLine());
			bags.add(volume);
		}

		Collections.sort(bags);

		PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
		long answer = 0;

		for (int i = 0, j = 0; i < K; i++) {
			while (j < N && jewels.get(j).weight <= bags.get(i)) {
				pq.add(jewels.get(j++).value);
			}

			if (!pq.isEmpty()) {
				answer += pq.poll();
			}
		}

		System.out.println(answer);
	}

	private static class Jewel {
		int weight;
		int value;

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