문제
N개의 과제가 있고, 각 과제는 마감일 d와 점수 w가 있다. 하루에 하나의 과제만 제출할 수 있으며, 마감일 이전에 제출해야 점수를 받는다. 받을 수 있는 점수의 최댓값을 구하라.
입력
첫째 줄에 과제의 수 N이 주어진다. (1 ≤ N ≤ 1,000) 이후 N개의 줄에 과제의 마감일 d와 점수 w가 주어진다. (1 ≤ d ≤ 1,000, 1 ≤ w ≤ 100)
출력
받을 수 있는 점수의 최댓값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 4 60 4 40 1 20 2 50 3 30 4 10 6 5 | 185 |
풀이
마감일 내림차순 정렬 후 우선순위 큐(최대 힙)를 사용하는 그리디 알고리즘을 적용한다.
- 과제를 마감일 내림차순(같으면 점수 내림차순)으로 정렬한다
- 최대 마감일(day)을 구한다
- day부터 1까지 반복하면서:
- 현재 날짜 i 이상인 마감일의 과제를 우선순위 큐에 추가
- 큐가 비어있지 않으면, 가장 점수가 높은 과제를 하나 꺼내어 점수 누적
- 모든 날짜 처리 후 누적된 점수 출력
핵심 아이디어: 마감이 늦은 날부터 역방향으로 탐색하며, 각 날짜에 제출 가능한 과제 중 가장 점수가 높은 것을 선택하는 그리디 전략이다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Day166BOJ13904그리디PQ { // 13904 정렬 그리디 우선순위 큐 구선생님 도움
static int N;
static int[][] paper;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
paper = new int[N][2];
int day = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
paper[i][0] = Integer.parseInt(st.nextToken());
paper[i][1] = Integer.parseInt(st.nextToken());
day = day < paper[i][0] ? paper[i][0] : day;
}
Arrays.sort(paper, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return (o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0]);
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
int j = 0, answer = 0;
for (int i = day; i > 0; i--) {
for (; j < N && paper[j][0] >= i; j++) {
pq.add(paper[j][1]);
}
if (!pq.isEmpty())
answer += pq.poll();
}
System.out.println(answer);
br.close();
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)