알고리즘/백준
[Java] 과제 - Greedy
Garonguri
2022. 2. 8. 13:22
728x90
https://www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class bj13904 {
static int N;
static int[][] homework;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
homework = new int[N+1][2];
int due=0;
for(int n=0;n<N;n++){
StringTokenizer st = new StringTokenizer(br.readLine());
homework[n][0] = Integer.parseInt(st.nextToken());
homework[n][1] = Integer.parseInt(st.nextToken());
due = Math.max(due, homework[n][0]);
}
int result =0;
for(int i=due;i>0;i--){
int idx = N;
int score =0;
//System.out.println("나는 지금 " + i + "일차다.");
for(int j=0; j<N; j++){
if(homework[j][0] >= i) {
if (score < homework[j][1]) {
score = homework[j][1];
idx = j;
}
}
}
//System.out.println("나는 " +(idx+1)+"번 과제를 지울것이다.");
result += score;
homework[idx][0] = 0;
}
System.out.println(result);
}
}
/**
* 마감 6일째부터 돌면서 1개씩 하기?
*/
|
cs |
음...
내가 지금 마지막날이라고 생각하고 마지막날에만 풀 수 있는 과제를 먼저 하고,
그 전날은 그 전날까지 할 수 있는 과제를 하고.. 이런 느낌으로 한다.
그 날 해야하는 과제가 여러 개가 있을 경우 가장 점수가 큰 과제를 우선적으로 한다.
* 과제가 끝났으면 과제 점수를 0점으로 바꿔준다. 그러면 다음번에 같은 과제를 탐색할 일이 없으며
(배열을 써서 이렇게 함. 리스트를 썼으면 remove를 해주었겠즹?)
다 풀고나니,, 우선순위 큐를 썼으면 좋았을 것 같아서 다시 풀어봐야지
728x90