[백준 P13904] 과제 Java

P13904 과제 Java

13904번: 과제

 

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

입력값

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

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

 

출력값

얻을 수 있는 점수의 최댓값을 출력한다.

185

 

알고리즘

문제 자체는 이해하는데 어렵지 않았다.

아마 이런 유형의 문제를 처음 풀이하는 분들은 아이디어를 떠올리는데 어려울 수는 있었을 것 같다.

 

우선, 크게 고민하지 않고 문제를 읽고 풀이한다고 생각해보자.

 

주어진 과제 정보는 데드라인과 그 과제를 해결했을 때 얻을 수 있는 점수이다.

하루에 한 가지 과제만 수행할 수 있으며, 과제 점수를 최대로 하고 싶기 때문에 뭔가 점수와 데드라인을 기준으로 정렬을 해야할 것으로 보인다. 그래서 데드라인을 내림차순으로 정렬하고 점수를 내림차순으로 정렬한다.

 

로직은 간단하다. 예시로 주어진 인풋을 살펴보자.

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

인풋을 데드라인 순으로 내림차순 정렬하고 점수 순으로 한번 더 내림차순 정렬하면 다음과 같아진다.

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

가장 데드라인이 긴 과제는 6일이다. 원래대로라면 1일, 2일, 3일, 4일, 5일, 6일 순으로 각 날짜에 해결할 수 있는 과제들 중 가장 큰 점수를 더해야 한다. 하지만 데드라인을 내림차순으로 정렬하였기에 6일부터 1일 순으로 해결할 수 있는 과제들 중 가장 큰 점수를 더하겠다.

 

1. 6일은 1개의 과제만 해결할 수 있다. 그래서 최종 값에 5를 더한다.
2. 5일은 해결할 수 있는 과제가 없다.
3. 4일은 3개의 과제를 해결할 수 있다. 그 중 60이 가장 크기 때문에 최종 값에 60을 더한다.
4. 3일이 중요하다. 데드라인이 3일인 과제는 1개가 있다. 하지만 3일에 해결할 수 있는 과제는 3개이다. 왜냐하면 4일에 해결할 수 있었지만 점수가 60인 과제를 해결하기 위해 미처 해결하지 못한 과제가 2개 남아있기 때문이다. 따라서 3일에는 4 40, 4 10, 3 30 중 점수가 큰 과제를 골라야 한다. 따라서 최종 값에 40을 더한다.
5. 데드라인이 2일인 과제는 1개가 있으며 2일에 해결할 수 있는 과제는 따라서 4 10, 3 30, 2 50이 된다. 최종 값에 50을 더한다.
6. 데드라인이 1일인 과제는 1개가 있으며 1일에 해결할 수 있는 과제는 따라서 4 10, 3 30, 1 20이 된다. 최종 값에 30을 더한다.

따라서 최종 결과는 5 + 60 + 40 + 50 + 30 으로 185이다.

 

여기서 해당 데드라인에 해결할 수 있는 모든 과제들을 모아두는 자료구조로 우선순위 큐를 사용했다. 따라서 각 데드라인 마다 새롭게 해결할 수 있는 과제들이 추가되더라도 O(log N)의 복잡도로 과제를 추가할 수 있고 그 안에서 점수가 가장 큰 과제를 선택하는 데에는 O(1) 밖에 걸리지 않는다.

 

물론 데드라인을 기준으로 오름차순 정렬을 한 뒤, 하루씩 돌아가면서 해결할 수 있는 과제를 우선순위 큐에 넣고 그 과제의 데드라인이 지났는지를 확인하며 점수를 계산해도 된다. 하지만 이 경우에는 점수 계산과 더불어 그 과제의 데드라인이 이미 지났는지도 확인해야 한다. 따라서 굳이 2번의 일을 하기보다는 애초에 내림차순으로 정렬하여 우선순위 큐에 들어오는 모든 과제가 데드라인과 상관 없도록 하는 것이 좋아보인다.

 

아래는 전체 코드이다.

 

코드

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

public class Main {
    static int N;
    static PriorityQueue<int[]> homeworks;
    static List<int[]> works;
    static int total;

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

        N = Integer.parseInt(br.readLine());
        homeworks = new PriorityQueue<>((a, b) -> {
            int comp = Integer.compare(b[1], a[1]);
            if (comp == 0) Integer.compare(b[0], a[0]);
            return comp;
        });
        works = new ArrayList<>();

        int maxDay = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int score = Integer.parseInt(st.nextToken());

            works.add(new int[] {day, score});
            maxDay = Math.max(maxDay, day);
        }

        works.sort((a, b) -> {return Integer.compare(b[0], a[0]);});

        int pointer = 0;
        for (int i = maxDay; i > 0; i--) {
            while (pointer < N && works.get(pointer)[0] == i) {
                homeworks.add(works.get(pointer++));
            }

            if (!homeworks.isEmpty()) {
                total += homeworks.poll()[1];
            }
        }

        System.out.println(total);
    }
}