문제
1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
알고리즘
그리디 알고리즘, 정렬, 우선순위 큐
풀이
N과 K가 30만으로 굉장히 크기 때문에 O(n2) 의 미만의 시간 복잡도로 해결해야한다.
이를 위해서 정렬과 우선순위 큐를 사용한다.
준비물
1. 남아있는 보석을 저장할 우선순위 큐 remains (무게 기준 오름차순 정렬)
2. 담을 수 있는 보석을 저장할 우선순위 큐 avails (비용 기준 내림차순 정렬)
3. 가방을 저장할 리스트 bags (가방 용량 기준 오름차순)
알고리즘
1. 이제 모든 보석을 remains에 삽입하고, 모든 가방을 bags에 삽입한 후 용량의 오름차순으로 정렬한다.
2. 이제 용량이 낮은 가방부터 탐색하며 remains에서 해당 가방의 용량보다 무게가 작은 보석을 꺼내 avails 큐에 삽입한다.
이렇게 하면 avails에 있는 맨 앞의 원소는 해당 가방에 담을 수 있는 보석 중 가장 가격이 비싼 보석이 된다.
3. 따라서 맨 앞의 원소를 꺼내 값을 더한다.
이제 다음 가방을 탐색해도 해당 가방의 용량보다 가벼운 보석들이 이미 avails 큐에 담겨있기 때문에 보석을 처음부터 탐색하지 않아도 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
private static final String ArrayList = null;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
PriorityQueue<Jewel> remains = new PriorityQueue<>((j1, j2) -> j1.m - j2.m);
PriorityQueue<Jewel> avails = new PriorityQueue<>((j1, j2) -> -(j1.v - j2.v));
ArrayList<Integer> bags = new ArrayList<>();
st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int M = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
remains.add(new Jewel(M, V));
}
for (int i = 0; i < K; i++) {
int C = Integer.parseInt(br.readLine());
bags.add(C);
}
Collections.sort(bags);
long sum = 0;
for(int i=0; i<K; i++) {
int cur = bags.get(i);
while(!remains.isEmpty() && remains.peek().m <= cur) {
avails.add(remains.poll());
}
if(!avails.isEmpty())
sum += avails.poll().v;
}
System.out.println(sum);
}
static class Jewel {
int m, v;
public Jewel(int m, int v) {
this.m = m;
this.v = v;
}
}
}
'Algorithm > 백준(BOJ)' 카테고리의 다른 글
[백준] 14890. 경사로 (Java) (1) | 2022.10.11 |
---|---|
[백준] 1368. 물대기 (Java) (0) | 2022.10.10 |
[백준] 12852. 1로 만들기 2 (Java) (0) | 2022.10.10 |
[백준] 1463. 1로 만들기 (Java) (0) | 2022.10.10 |
[백준] 1806. 부분합 (Java) (0) | 2022.10.10 |