import java.util.*;
import java.io.*;
public class Main {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static StringTokenizer st;
public static int INF = 100_000_000;
public static int[] dx = {0,1,0,-1};
public static int[] dy = {-1,0,1,0};
public static class Crystal{
int mass;
int value;
public Crystal() {}
public Crystal(int mass, int value) {
this.mass = mass;
this.value = value;
}
@Override
public String toString() {
return "Crystal [mass=" + mass + ", value=" + value + "]";
}
}
public static void main(String[] args) throws IOException{
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
List<Crystal> list = new ArrayList<>();
int[] backpack = new int[M];
for(int i = 0 ; i < N; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
list.add(new Crystal(m,v));
}
Collections.sort(list,(a,b) -> a.mass - b.mass);
for(int i = 0; i < M; i++) {
int size = Integer.parseInt(br.readLine());
backpack[i] = size;
}
Arrays.sort(backpack);
int listIdx = 0;
long answer = 0;
PriorityQueue<Crystal> pq = new PriorityQueue<>((a,b) -> b.value - a.value);
for(int i = 0 ; i < M; i++) {
while(listIdx < N && list.get(listIdx).mass <= backpack[i]) {
Crystal cur =list.get(listIdx++);
pq.add(new Crystal(cur.mass,cur.value));
}
if(!pq.isEmpty()) answer+=pq.poll().value;
}
System.out.println(answer);
}
}
문제 풀이
해당 문제는 간단한 그리디 문제로 보이지만 일차원적으로 그리디로만 푼다면 쉽게 풀 수 있지만, 시간복잡도에서 통과하기가 쉽지 않은 문제였다.
처음에 풀 때, 우선 순위 큐를 사용하여 해당 무게에서 최대로 챙길 수 있는 무게를 구했지만 시간 초과가 떴다.
이 후 추가적으로 tempPq를 생성하여 최적의 보석을 제거하고 다시 pq에 넣어가며 두개의 우선 순위 큐를 사용해보았지만 이 방법으로도 시간 초과가 떴다.
이 문제에서 효율적으로 그리디를 진행하기 위해서는 리스트와 우선순위 큐를 같이 사용하는 것이다.
문제 풀이 과정은 아래와 같다.
처음에 풀 때는 Class에 compareTo 메서드를 설정하여 하나의 기준으로 정렬을 하였지만 위 과정에서는 리스트와 우선 순위 큐의 조건을 다르게 설정하여 풀었다.
풀이 코드