백준 13904번 - 과제

문제

백준 13904번 - 과제

---

아이디어

• 우선 점수를 최대한 많이 받기 위해 점수를 기준으로 내림차순 정렬한다.
• 그 다음 가장 많이 받을 수 있는 점수부터 마감일을 넘지 않고 최대한 마감일에 가깝게 해당 과제를 처리한다.
• 예제 입력을 기준으로 위 과정은 다음과 같다.

점수 내림차순 정렬

점수를 가장 많이 받는 4일짜리 60점부터 처리

그 다음 2일짜리 50점 처리

다음 4일짜리 40점을 처리해야 하는데 이미 4일에는 더 높은 점수를 처리했으므로, 3일에 처리(4일은 넘으면 안됨)

다음 3일짜리 30점도 3일도 이미 처리됐고 2일도 이미 처리됐기 때문에 1일까지 내려감

다음 1일과 4일은 처리할 수 없다. 이미 마감일 내에 처리될 수 있는 높은 점수가 처리되었다.

다음 6일짜리 5점 처리

• 이 값들을 모두 합한 값이 정답이다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N x d)

코드 구현

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

public class BJ_13904 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] tasks = new int[n][2];
        int maxDay = 0;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            tasks[i][0] = d;
            tasks[i][1] = w;

            maxDay = Math.max(maxDay, d);
        }

        Arrays.sort(tasks, (o1, o2) -> o2[1] - o1[1]);

        int sum = 0;
        int[] arr = new int[maxDay + 1];

        for (int[] task : tasks) {

            int d = task[0];
            int w = task[1];

            for (int i = d; i > 0; i--) {
                if (arr[i] == 0) {
                    arr[i] = w;
                    sum += w;
                    break;
                }
            }
        }

        System.out.println(sum);
    }
}