[그리디] 백준 13904번 과제 java 풀이

https://www.acmicpc.net/problem/13904

 

푸는 법은 단순합니다. 

1. [마감 날짜, 점수] 배열을 저장하는 이중 배열 선언
2. 그리고 점수를 내림차순 정렬 한다
3. 날짜 별로 해결한 과제의 점수를 저장하는 배열 선언  
4. 이중 배열을 순회하면서 날짜 별로 가장 높은 점수를 3번에서 선언한 배열에 저장한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] tasks = new int[n][2];
        int last = -1; // 가장 오래걸리는 과제 일수
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int point = Integer.parseInt(st.nextToken());
            tasks[i][0] = day;
            tasks[i][1] = point;
            last = Math.max(last, day);
        }
        Arrays.sort(tasks, (o1, o2) -> o2[1] - o1[1]); // 과제 점수 가장 높은 것부터 내림차순 정렬
        int[] isCompleted = new int[1001]; // 각 날짜 별로 푼 과제의 점수를 저장하는 배열
        for (int[] task : tasks) {
            for (int currentDay = task[0]; currentDay > 0; currentDay--) {
                if (isCompleted[currentDay] == 0) { // 만약 현재 날짜에 과제 점수가 저장이 안 되어있다면 
                    isCompleted[currentDay] = task[1]; // 현재 날짜에 푼 과제 점수를 기록
                    break; // 점수를 내림차순으로 정렬했으므로, 이 날짜에 푼 과제 점수가 가장 높은 점수
                } // 이 날 이미 가장 높은 점수의 과제를 수행했다면, currentDay--를 하여 그 전날에는 가능한지 검사
            }
        }

        int score = 0;
        for (int s : isCompleted) {
            score += s;
        }
        System.out.println(score);
    }
}