문제
N개의 보석과 K개의 가방이 있다. 각 보석은 무게 M과 가격 V를 가지며, 각 가방은 최대 무게 C를 담을 수 있다. 각 가방에는 보석을 최대 1개만 넣을 수 있을 때, 훔칠 수 있는 보석 가격의 최대합을 구한다.
입력
첫째 줄에 N, K(1 ≤ N, K ≤ 300,000)가 주어진다. 다음 N개의 줄에 보석의 무게 M과 가격 V(1 ≤ M, V ≤ 1,000,000)가 주어진다. 다음 K개의 줄에 가방의 최대 무게 C(1 ≤ C ≤ 100,000,000)가 주어진다.
출력
훔칠 수 있는 보석 가격의 최대합을 출력한다.
예제
입력
2 1
5 10
6 12
10출력
12풀이
핵심 아이디어: 보석을 가격 내림차순으로 정렬하고, 가방 무게를 TreeMap으로 관리한다. 가격이 높은 보석부터 순서대로, 해당 보석을 담을 수 있는 가방 중 가장 작은 가방(ceiling)에 넣는 그리디 전략을 사용한다.
- 보석을 가격 내림차순(가격이 같으면 무게 오름차순)으로 정렬한다.
- 가방 무게를
TreeMap<무게, 개수>에 저장한다. - 가격 높은 보석부터 순회하면서:
map.ceilingKey(weight)로 보석 무게 이상의 가방 중 가장 작은 용량의 가방을 찾는다.- 해당 가방이 있으면 해당 보석을 담고, 가방 카운트를 1 감소(0이 되면 제거)한다.
- 총합에 보석 가격을 더한다.
- 모든 보석을 확인한 후 총합을 출력한다.
TreeMap.ceilingKey()는 O(log K) 시간이므로, 전체 시간 복잡도는 O(N log N + N log K)이다.
코드
import java.util.*;
import java.io.*;
public class Day361BOJ1202보석도둑 {
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]);
int[][] items = new int[n][2];
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++) {
String[] mv = br.readLine().split(" ");
items[i][0] = Integer.parseInt(mv[0]);
items[i][1] = Integer.parseInt(mv[1]);
}
Arrays.sort(items, (int[] a1, int[] a2) -> {
if (a1[1] == a2[1])
return a1[0] - a2[0];
else
return a2[1] - a1[1];
});
for (int i = 0; i < k; i++) {
int weight = Integer.parseInt(br.readLine());
map.put(weight, map.getOrDefault(weight, 0) + 1);
}
long sum = 0;
for (int i = 0; i < n; i++) {
int weight = items[i][0];
int value = items[i][1];
if (map.ceilingKey(weight) == null)
continue;
int temp = map.ceilingKey(weight);
int count = map.get(temp);
if (count > 1)
map.put(temp, count - 1);
else
map.remove(temp);
sum += value;
}
System.out.print(sum);
}
}복잡도
- 시간: O(N log N + N log K) — 정렬 + TreeMap 탐색
- 공간: O(N + K) — 보석 배열 및 가방 TreeMap