문제
N개의 문제가 각각 데드라인과 컵라면 수를 가질 때, 시간 1에 문제 1개를 풀 수 있다면 받을 수 있는 최대 컵라면 수를 구하라.
입력
첫째 줄에 N, 이후 N줄에 데드라인과 컵라면 수가 주어진다.
출력
최대 컵라면 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 1 6 1 7 3 2 3 1 2 4 2 5 6 1 | 15 |
풀이
데드라인 순으로 정렬하고, 최소 힙으로 보상이 작은 문제를 교체하며 최대 보상을 유지한다.
- 데드라인 오름차순으로 정렬한다
- 각 문제를 최소 힙에 넣는다
- 힙 크기가 데드라인을 초과하면 가장 작은 보상을 제거한다
- 최종적으로 힙에 남은 보상의 합이 답이다
핵심 아이디어: 데드라인 d인 문제는 최대 d개까지 선택할 수 있으므로, 힙 크기를 데드라인으로 제한하면 항상 최적의 조합이 유지된다.
코드
package day549;
import java.util.*;
import java.io.*;
public class Day510BOJ1781컵라면 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<int[]> al = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
al.add(new int[] { a, b });
}
Collections.sort(al, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] > o2[0]) {
return 1;
} else if (o1[0] < o2[0]) {
return -1;
} else {
return 0;
}
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
pq.offer(al.get(i)[1]);
if (pq.size() > al.get(i)[0]) {
pq.poll();
}
}
int ans = 0;
while (!pq.isEmpty()) {
ans += pq.poll();
}
System.out.println(ans);
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)