[백준 13904 / JAVA] 과제

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

13904번: 과제

 

2가지 방식을 생각했다.

 

첫번째 방식

날짜를 뒤에서 부터 생각하며 각 날짜마다 가장 높은 과제를 풀도록 하는 방식

예제 1번을 예시로 하면 가장 마지막 마감일이 6일이다.

6일에 할 수 있는 과제 중 가장 큰 과제는 마지막 과제이므로 +5

5일에 할 수 있는 과제는 없다.

4일에 할 수 있는 과제 중 가장 큰 과제는 첫번째 과제이므로 +60

3일에 할 수 있는 과제 중 가장 큰 과제는 두번째 과제이므로 +40

2일에 할 수 있는 과제 중 가장 큰 과제는 네번째 과제이므로 +50

1일에 할 수 있는 과제 중 가장 큰 과제는 다섯번째 과제이므로 +30

총 185이다.

 

두번째 방식

입력 받은 값들을 점수가 높은 순서대로 정렬하고 점수 순서대로 처리한다.

정렬하면 4 60 / 2 50 / 4 40 / 3 30 / 1 20 / 4 10 / 6 5 의 순서로 정렬된다.

 

가장 높은 점수를 가진 첫번째 과제를 본다. 마감일이 4일이므로 4일에 처리한다.

다음으로 네번째 과제를 본다. 마감일이 2일 이므로 2일에 처리한다.

다음으로 두번째 과제를 본다. 마감일이 4일이지만 4일에는 이미 할 과제가 있다.

3일로 당긴다. 3일에 처리한다.

다음으로 다섯 번째 과제를 본다. 마감일이 3일이지만 3일과 2일 모두 이미 할 과제가 있다.

1일로 당겨서 처리한다.

다음으로 세번째 과제를 본다. 마감일이 1일이지만 이미 1일에 처리할 과제가 있다. 포기한다.

다음으로 여섯 번째 과제를 본다. 마감일이 4일이지만 이미 1, 2, 3, 4일에 처리할 과제가 모두 있다. 포기한다.

마지막으로 일곱 번째 과제를 본다. 마감일이 6일이다, 6일에 처리한다.

총 185이다.

 

처음에는 첫번째 방식으로 하려 했지만 막상 구현하려하니 두번째 방식이 더 간단한 것 같아서 두번째 방식으로 했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] a;
    static int[] score = new int[1001];
    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String input;
        int N;

        N = Integer.parseInt(br.readLine());

        a = new int[N][2];

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

        //점수 순서대로 정렬
        Arrays.sort(a, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1])
                    return o2[1] - o1[1];
                return o2[1] - o1[1];
            }
        });

        for (int i = 0; i < N; i++) {
            for (int j = a[i][0]; j > 0; j--) {
                //현재 마감일에 할 과제가 없다면
                if (score[j] == 0) {
                    score[j] = a[i][1];
                    result += a[i][1];
                    break;
                }
            }
        }

        System.out.println(result);
    }

}