[BOJ] 13904번 - 과제 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

이 문제에서 핵심은 마감기한이다.

우선 당연히 점수가 최대로 되려면 과제에 부여된 점수가 큰 것을 해야한다.

하지만 마감기한이 지나면 아무리 높아도 쓸 수 없다.

입력된 예제를 정렬한 경우

위의 그림과 같이 예제를 2가지 방법으로 정렬해보았다

• 마감기한을 오름차순으로 정렬, 마감기한이 같으면 점수는 내림차순으로 정렬
• 마감기한을 내림차순으로 정렬, 마감기한이 같으면 점수는 내림차순으로 정렬

1. 마감기한을 오름차순으로 정렬한 후 1일부터 확인하기

• 1일째 : 1, 2, 3, 4, 4, 4, 6
• 2일째 : 2, 3, 4, 4, 4, 6
• 3일째 : 3, 4, 4, 4, 6
• 4일째 : 4, 4, 4, 6
• 5일째 : 6
• 6일째 : 6

수행할 수 있는 과제는 과제를 수행하는 날짜에 따라 다르다.

1일째에 어느 문제를 해결해야 최대 점수가 되는지 확인하려면 6일째까지 탐색해봐야지만 알 수 있다.

즉, 얻을 수 있는 최대 점수를 확인하기 위해 많은 경우의 수를 탐색해야 한다.

 

2. 마감기한을 내림차순으로 정렬한 후 가장 마지막 날부터 확인하기

이전에 앞에서부터 탐색하는 것이 아니라 뒤에서부터 탐색하여 경우의 수를 줄여 문제를 해결한 적이 있다.

[BOJ] 12919번 - A와 B 2 (Java)

• 6일째 : 6
• 5일째 : 6
• 4일째 : 4, 4, 4, 6
• 3일째 : 3, 4, 4, 4, 6
• 2일째 : 2, 3, 4, 4, 4, 6
• 1일째 : 1, 2, 3, 4, 4, 4, 6

뒤집기만 했을 뿐인데 경우의 수가 줄어든 것이 보일 것이다.

6일째에 가장 점수를 최대로 얻을 수 있는 과제를 수행하고 5일째에는 할 수 있는 과제가 없으니 넘어간다.

4일째에는 수행한 과제를 제외하고 최대 점수를 얻을 수 있는 과제를 하면 된다.

즉, 하루하루 줄여가며 그때그때 최대 점수를 찾아내면 되는 것이다.

 

이제 문제는 어떻게 최대 점수를 찾아낼 것이냐? 이다.

나는 날을 줄여가면서 할 수 있는 과제의 점수들을 최대힙에 넣어 사용하기로 했다.

그러면 언제든지 최댓값을 뽑아낼 수 있을 것이다.

PriorityQueue<Integer> heap = new PriorityQueue<>();

 

위의 코드는 자바에서 우선순위 큐를 이용하여 힙을 선언한 것이다.

이는 기본적으로 최소힙이기 때문에 최대힙으로 사용하기 위해 넣어 주는 값에 음수를 취하기로 했다.

int score = 0;
int idx = 0;
for(int day = assignments[0][0]; day > 0; day--) { //최대 마감 기한이 먼 날부터
    while (idx < assignments.length && assignments[idx][0] >= day) { //가능한 과제들의 점수 넣기
        heap.offer(-assignments[idx][1]);
        idx++;
    }
    if(!heap.isEmpty()) {
        score -= heap.poll(); //음수로 입력되었기 때문에 빼준다.
    }
}

 

가장 먼 마감 기한부터 하루씩 줄여가면서 수행할 수 있는 과제들의 점수를 최대힙에 넣는다.

힙이 비어있지 않는 한 하루에 한개의 과제를 수행해야 하므로 가장 높은 점수를 빼서 결과를 구한다.

 

그동안 자료구조를 공부하면서 알고는 있었지만 생각하지 못할 때가 많았다.

이번에는 최대힙을 이용하여 변하는 리스트에서 최댓값을 뽑아낸다는 생각이 나면서 뿌듯했다.

또한 저번에 정리했던 내용이 리마인드되면서 문제를 해결할 수 있어서 더욱 뿌듯했다.

---

🍀 풀이 🍀

package Baekjoon;

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

public class Greedy13904 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] assignments = new int[n][2];

        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            assignments[i][0] = Integer.parseInt(st.nextToken());
            assignments[i][1] = Integer.parseInt(st.nextToken());
        }
        System.out.println(getMaxScore(assignments));
    }

    public static int getMaxScore(int[][] assignments) {
        //마감일이 먼 것부터, 같으면 점수가 높을 것부터 정렬
        Arrays.sort(assignments, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o2[0] - o1[0] == 0) {
                    return o2[1] - o1[1];
                }
                return o2[0] - o1[0];
            }
        });

        PriorityQueue<Integer> heap = new PriorityQueue<>(); //최소힙이므로 점수를 음수로 입력한다.
        int score = 0;
        int idx = 0;
        for(int day = assignments[0][0]; day > 0; day--) {
            while (idx < assignments.length && assignments[idx][0] >= day) {
                heap.offer(-assignments[idx][1]);
                idx++;
            }
            if(!heap.isEmpty()) {
                score -= heap.poll(); //음수로 입력되었기 때문에 빼준다.
            }
        }
        return score;
    }
}