https://www.acmicpc.net/problem/2109
2109번: 순회강연
한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다.
www.acmicpc.net
문제

풀이
이전에 풀었던 컵라면 문제와 동일하다. https://katastrophe.tistory.com/73
1. 기간순으로 오름차순 정렬된 우선순위 큐(q1)에 삽입
2. 페이 순으로 오름차순 정렬된 우선순위 큐(q2)에 삽입
2_1. 삽입한 원소의 기간보다 q2의 사이즈가 더 크면 큐의 맨 앞의 원소를 poll. ( 더 적은 페이를 제거 )
3. q2를 순회하면서 전부 합산
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
import java.util.*;
import java.io.*;
import java.util.stream.*;
import static java.util.Arrays.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue<int[]> list = new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
for(int i=1;i<=n;i++)
list.add(stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt).toArray()); // pay , day
Queue<Integer> q = new PriorityQueue<>();
while (!list.isEmpty()){
int[] cur = list.poll();
q.add(cur[0]); // cur.pay
if(q.size() > cur[1]) q.poll(); //cur.day
}
int ans=0;
while (!q.isEmpty()) ans+=q.poll();
System.out.println(ans);
}
}
|
cs |

'알고리즘,PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 [14889] 스타트와 링크 JAVA (0) | 2021.11.29 |
|---|---|
| [BOJ] 백준 [6603] 로또 JAVA (0) | 2021.11.29 |
| [BOJ] 백준 [3977] 축구전술 JAVA (0) | 2021.11.25 |
| [BOJ] 백준 [4013] ATM JAVA (0) | 2021.11.23 |
| [BOJ] 백준 [4196] 도미노 JAVA (0) | 2021.11.23 |