[백준]13904: 과제 - JAVA
[백준]13904: 과제
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
풀이
🪑 골드 문제 이길래 처음에 괜히 어렵게 생각해서 DP인가.. 했는데 그냥 구현문제였다.
📝 문제를 정리해 보자!
- 하루에 하나의 과제를 할 수 있다.
- 과제를 마무리 할 때마다 마무리한 과제의 점수를 얻는다.
🔧 문제를 풀어보자!
- 입력받은 과제들의 정보를 날짜 순서대로 내림차순 한다.
- 제일 마지막 날짜에서 부터 가능한 과제를 하나씩 우선순위 큐에 넣어준다.
- 우선순위 큐에서 가장 큰 점수를 갖는 과제를 하나씩 꺼내어 결과에 더해준다.
🙋♀️ 일단 예제를 함께 따라가 보자. 어떤 로직으로 풀지 생각해 보는 과정이다.
- 과제는 순서대로 첫 번째 과제부터 1번 과제라고 부를 것이다.
- 각 날짜 별로 해결할 수 있는 과제는 다음과 같다.
6일) 7
5일) 7
4일) 1 2 6 7
3일) 1 2 5 6 7
2일) 1 2 4 5 6 7
1일) 1 2 3 4 5 6 7
이때 풀 수 있는 과제 순서대로 가장 큰 점수를 갖는 과제를 선택한다면 7, 1, 2, 4, 5 순서대로 선택할 수 있으며 우리가 원하는 정답이 된다. 이제 식으로 풀어내 보자!
🔹 입력받은 과제들의 정보를 날짜 순서대로 내림차순 한다.
- 내림차순 하여 마지막 날짜부터 현재 풀 수 있는 과제인지 확인해 줄 것이다.
- 이때 마지막 날짜는 입력받는 날짜 중에서 가장 큰 날이 된다.
🔹 제일 마지막 날짜에서 부터 가능한 과제를 하나씩 우선순위 큐에 넣어준다.
- 우선순위 큐는 점수 순서대로 내림차순 되도록 설정되어 있다.
- 현재 날짜랑 비교하여 날짜 순서대로 내림차순 되어있는 과제 리스트의 값과 비교한 후 현재 날짜보다 크거나 같아야 풀 수 있는 과제이므로 큐에 담아준다.
🔹 우선순위 큐에서 가장 큰 점수를 갖는 과제를 하나씩 꺼내어 결과에 더해준다.
- 현재 풀 수 있는 과제 중에서 가장 큰 점수를 갖는 과제의 정보는 우선순위큐의 맨 앞에 있다.
코드
|
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
//입력
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bf.readLine());
Node[] works = new Node[n];
int last_day = -1;
for(int i = 0; i < n; i++) {
String str = bf.readLine();
StringTokenizer st = new StringTokenizer(str);
int d = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
works[i] = new Node(d, c);
last_day = Math.max(last_day, d);
}
//입력 끝
Arrays.sort(works, (o1, o2) -> o2.day - o1.day); //날짜 순 내림차순
int result = 0;
int works_idx = 0;
PriorityQueue<Node> q = new PriorityQueue<>();
for(int i = last_day; i > 0; i--) {
while(works_idx < n && works[works_idx].day >= i) {
q.offer(works[works_idx++]);
}
if(!q.isEmpty()) result += q.poll().score;
}
System.out.println(result);
}
public static class Node implements Comparable<Node> {
int day;
int score;
public Node(int day, int score) {
this.day = day;
this.score = score;
}
@Override
public int compareTo(Node n) {
return n.score - this.score;
}
}
}
|
cs |