한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.
첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10
185
package baekjoon;
import java.util.*;
// 그리디 알고리즘
public class B2109 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 행은 각 강연 요청을 구분하며 열은 각 강연 요청 당 마감일과 페이를 각각 나타낸다.
int[][] lectures = new int[n][2];
// reverseOrder(내림차순)속성을 갖는 Comparator객체를 PriorityQueue에 전달하여
// 높은 값이 우선순위를 갖는 Queue객체 생성
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
for(int i = 0; i < n; i++){
lectures[i][1] = sc.nextInt();
lectures[i][0] = sc.nextInt();
}
// deadline에 대해 내림차순 정렬
Arrays.sort(lectures, (a, b) -> b[0] - a[0]);
int maxMoney = 0;
int j = 0;
for(int i = 10000; i >= 1; i--){ // 강연 일수의 최대값인 10000부터 1까지
// 같은 deadline을 가진 강의들을 모두 heap에 추가
// j가 전체 강연요청 수 n보다 작으면서
// 각 강연의 마감일이 현재 탐색 중인 날짜 i보다 크거나 같다면(즉 아직 마감이 안됐다면)
while(j < n && lectures[j][0] >= i){
// 해당 강연의 강연료를 저장한다.
maxHeap.add(lectures[j][1]);
// 다음 강연요청으로 넘어간다.
j++;
}
// 10000일의
/*
위 코드에서 j는 강연 요청을 확인한 수를 나타낸다.
강연 요청은 마감일 기준으로 내림차순으로 이미 정렬이 되어있다.
따라서 j번째 강연 요청의 마감일이 현재 탐색중인 날짜 i 전이라면(작다면)
더 이상 현재 날짜에 대해 확인해야 할 강연 요청은 없는 것이다.
j 번째 강연 요청의 마감일이 탐색중인 날짜 이후(같거나 크다면)
이 강연 요청은 현재 날짜에 대해 확인해야 하는 강연 요청이다.
이 강연 요청들은 모두 우선순위 큐에 추가하고 가장 높은 강연료를 가진 강연을 선택한다.
*/
// 가장 비싼 강의 선택
if(!maxHeap.isEmpty()){
maxMoney += maxHeap.poll();
}
}
System.out.println(maxMoney);
}
}