[BOJ] 13904. 과제 (🥇, 그리디/우선순위 큐)

🔗

풀이

1202. 보석도둑 과 유사한 문제.

며칠 내에 과제를 해결해야 하는지 기한이 주어지지 않으므로 주어지는 과제들 가운데 최대 마감일을 기한으로 정하면 된다. 어차피 그 이상의 기한을 줘 봤자 수행할 수 있는 과제가 없기 때문에.

문제 예제에서는 6일이 최대이기 때문에 이 문제에 대해선 6일을 마지막 과제 마감 기한일이라고 정한다. 그러면 사실상 6일 차에 해결할 수 있는 과제는 (6, 5) 밖에 없다. 5일 차에는 마감일이 5일 이상인 과제들이 없으므로(6일 차의 과제는 6일차에 해결할거니까 제외) 넘어간다. 4일 차에는 3개의 과제가 있는데 최대값을 구하는 문제이니까 최대 점수를 얻을 수 있는 과제를 해결한다. (4, 60) 과제가 해결된다. 다음은 3일차인데 (3, 30) 과제가 추가되지만 과제 마감일이 3일 이상인 과제들 가운데 (4, 40)이 최대 점수 이므로 이 문제를 해결한다. 다음은 2일차로 과제 마감일이 2일 이상인 과제들 가운데 최대값을 고르면 (2, 50)이다.

이런식으로 과제 마감 기한일에서 1일차로 가는 거꾸로 풀이하는 방식으로 풀이하면 된다. 이유는 마감 기한일을 넘기면 점수를 얻을 수 없기 때문에 뒤로 갈수록 해결할 수 있는 문제들의 수에 한계가 생기기 때문이다. 그래서 적은 수의 선택지가 있는 것에서부터 최대값을 구하고 점점 범위를 늘려가야 그리디하게 풀 수 있다.

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

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[][] assignment = new int[N][2];
        for (int i = 0; i < N; i++) {
            assignment[i][0] = sc.nextInt();
            assignment[i][1] = sc.nextInt();
        }

        Arrays.sort(assignment, (a, b) -> {
            if (a[0] != b[0]) return b[0] - a[0];
            return b[1] - a[1];
        });

        int finalDay = assignment[0][0];
        int idx = 0;
        int maxScore = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        while (finalDay > 0 && idx < N) {

            while (idx < N && finalDay == assignment[idx][0]) {
                queue.add(-assignment[idx][1]);
                idx++;
            }
            System.out.println(queue);

            if (!queue.isEmpty()) {
                maxScore -= queue.poll();
            }
            finalDay--;
        }
        System.out.println(maxScore);
    }
}