[Gold II] 보석 도둑 - 1202
성능 요약
메모리: 318004 KB, 시간: 2400 ms
분류
자료 구조(data_structures), 그리디 알고리즘(greedy), 우선순위 큐(priority_queue), 정렬(sorting)
문제 설명
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 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)
모든 숫자는 양의 정수이다.
출력
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
풀이
처음에 푼 방식도 논리는 맞았지만, 시간 초과가 났다.
처음에는 보석을 val 순으로 내림차순 정렬하고, 가방을 무게 순으로 정렬한 후, val이 높은 보석부터 가방에 들어갈 위치를 찾았다
보석은 자신의 무게보다 크거나 같은 가방 중 가장 작은 가방을 찾는 것이 최선이기 때문에, 이분 탐색을 통해 보석이 들어갈 인덱스를 찾으려고 했다. 그런데 이 방식을 하면 ArrayList를 사용할 경우 보석이 들어간 가방을 지울 때 O(n)이 소요되어 시간 초과가 발생한다.
그래서 관점을 바꿔서 가방을 하나씩 탐색하며 가방에 들어갈 수 있는 보석 중 val이 가장 큰 보석을 넣도록 하였다.
1. 가방을 오름차순 정렬
2. 보석을 무게 기준 오름차순 정렬 (무게가 같으면 val 기준 내림차순 정렬)
3. 가방을 하나씩 훑으며 가방의 무게보다 작은 보석을 모두 priority queue에 넣음, 이때 보석은 무게 순으로 정렬된 상태이기 때문에 한 번 pq에 넣은 보석은 다시 확인할 필요가 없어짐
4. pq가 비어있지 않다면 poll한 보석이 해당 가방에 들어갈 수 있는 val이 최대인 보석이 된다.
package BOJ.Gold.g2;
import java.util.*;
public class BOJ_1202_보석도둑 {
static class Jewel implements Comparable<Jewel> {
int weight;
int val;
public Jewel(int weight, int val) {
this.weight = weight;
this.val = val;
}
@Override
public int compareTo(Jewel o) {
return this.val - o.val;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
// 보석을 무게 기준 오름차순 정렬
// 가방을 오름차순 정렬
// 가방을 훑으면서 가방의 무게보다 작거나 같은 보석 중 가장 val이 큰 보석을 더하기
Jewel[] jewels = new Jewel[N];
for (int i = 0; i < N; i++)
jewels[i] = new Jewel(sc.nextInt(), sc.nextInt());
Arrays.sort(jewels, (o1, o2) -> {
if (o1.weight == o2.weight) {
return o2.val - o1.val;
}
return o1.weight - o2.weight;
});
int[] bag = new int[K];
for (int i = 0; i < K; i++)
bag[i] = sc.nextInt();
Arrays.sort(bag);
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
long ans = 0;
int idx = 0;
for (int i = 0; i < K; i++) {
while (idx < N && jewels[idx].weight <= bag[i]) {
pq.add(jewels[idx].val); // pq에 val 추가
idx++;
}
if (!pq.isEmpty()) {
ans += pq.poll();
}
}
System.out.println(ans);
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 2573 - 빙산 (자바 Java) (0) | 2022.11.20 |
---|---|
[백준] 1937 - 욕심쟁이 판다 (자바 Java) (0) | 2022.11.08 |
[백준] 16946 - 벽 부수고 이동하기 4 (자바 Java) (0) | 2022.11.01 |
[백준] 1644 - 소수의 연속합 (자바 Java) (0) | 2022.10.30 |
[백준] 1806 - 부분합 (자바 Java) (0) | 2022.10.30 |