[JAVA] 백준, 13904번 과제

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

 

문제 풀이

List에 int[] 형태(day, 점수)로 값을 모두 저장하고 1차원 배열 값(day)을 기준으로 오름차순으로 정렬한다.

 

day의 초기값에는 과제의 기간이 가장 긴 날짜를 저장한다. 반복문에서는 0 ~ N까지 모든 과제를 돌면서 제출 기간이 남은 과제를 찾는다. 

기간이 아직 남은 과제 중에서 점수를 가장 많이 주는 과제를 찾으면 된다.

 

ex)

입력 :

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

입력받은 값을 day를 기준으로 오름차순 정렬한다.

1 20
2 50
3 30 
4 60 
4 40
4 10
6 5

 

먼저 과제 제출 기간이 가장 많이 남은 6을 day에 저장한다.

• 6일 보다 기간이 긴 과제는 없으므로 sum + 5를 한다. -> sum = 5
• 점수를 더한 과제는 0점으로 수정한다. 즉 6:5 -> 6:0으로 변경한다. (기간:점수)
• day를 1 감소시킨다. -> day = 5
• 5일 이상 남은 과제는 1개밖에 없으나, 해당 과제는 이전에 이미 점수를 추가한 과제이므로 sum + 0을 한다. -> sum  = 5
• day를 1 감소시킨다. -> day = 4
• 4일 이상 남은 과제는 4개가 있다. -> 4:60, 4:40, 4:10, 6:5
• 4개의 과제 중에서 점수가 가장 큰 60점을 sum에 더한다. -> sum = 65
• day를 1 감소시킨다. -> day = 3

위 과정을 day가 0이 될 때까지 반복한다.

코드

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static List<int[]> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.add(new int[]{a, b});
        }

        Collections.sort(list, (a, b) -> a[0] - b[0]);

        int day = list.get(N - 1)[0];
        int sum = 0;
        while (day > 0) {
            int maxValue = 0, maxDay = -1;
            for (int i = 0; i < N; i++) {
                if (list.get(i)[0] >= day && maxValue <= list.get(i)[1]) {
                    maxValue = list.get(i)[1];
                    maxDay = i;
                }
            }
            sum += maxValue;
            list.get(maxDay)[1] = 0;
            day--;
        }

        System.out.println(sum);
    }
}