문제
N개의 대학에서 강연 제안을 받으며 각각 보수와 마감일이 있다. 하루에 한 강연만 가능할 때, 최대 수입을 구하라.
입력
첫째 줄에 N, 이후 N줄에 보수와 마감일이 주어진다.
출력
최대 수입을 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10 | 185 |
풀이
마감일이 큰 것부터 역순으로 탐색하며, 최대 힙에서 가장 높은 보수를 선택한다.
- 마감일별로 강연을 분류한다
- 가장 큰 마감일부터 1일까지 역순으로 탐색한다
- 해당 마감일의 강연을 최대 힙에 추가하고 힙의 최댓값을 선택한다
핵심 아이디어: 늦은 날짜부터 채워나가면 마감일이 이른 강연은 이후에도 선택 기회가 있으므로 최적이 보장된다.
코드
package day699;
import java.io.*;
import java.util.*;
public class Day673BOJ2109순회강연 {
static int N;
static ArrayList<Integer>[] al;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
al = new ArrayList[10001];
for (int i = 1; i < 10001; i++) {
al[i] = new ArrayList<>();
}
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int pay = Integer.parseInt(st.nextToken());
int days = Integer.parseInt(st.nextToken());
al[days].add(pay);
}
int result = 0;
for (int i = 10000; i > 0; i--) {
for (int j = 0; j < al[i].size(); j++) {
pq.add(al[i].get(j));
}
if (!pq.isEmpty())
result += pq.poll();
}
System.out.println(result);
}
}복잡도
- 시간: O(D + N log N) - D는 최대 마감일
- 공간: O(D + N)