문제 설명
문제 풀이
- 우선 입력을 배열로 만들고 데드라인 오름차순, 보상개수 내림차순으로 정렬한다.
- 배열 앞에서 부터 컵라면 개수를 대상으로하는 우선순위 큐에 보상개수를 넣어주되 큐 사이즈가 데드라인을 넘어서게 되면 poll을 해준다. (PQ가 해당 데드라인까지 가능한 모든 보상에 대한 고려를해서 작은 것들만 빼준다고 보면됨)
소스 코드 (JAVA)
import java.io.*;
import java.util.*;
public class Main {
static class Point implements Comparable<Point>{
int d, c;
public Point(int d, int c) {
this.d = d;
this.c = c;
}
@Override
public int compareTo(Point o) {
if (this.d > o.d) return 1;
else if (this.d < o.d) return -1;
else {
if (this.c < o.c) return 1;
else if (this.c > o.c) return -1;
else return 0;
}
}
}
static int N;
static Point[] arr;
static void solve() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
arr = new Point[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
Arrays.sort(arr);
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
pq.add(arr[i].c);
if (arr[i].d < pq.size()) pq.poll();
}
int result = 0;
while(!pq.isEmpty()) result += pq.poll();
bw.write(result + "\n");
bw.flush();
}
public static void main(String[] args) throws IOException {
solve();
}
}