(백준) 13904 - 과제 [java]

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

 

🐢 설명

디데이와 포인트가 있는 숙제들에 대해서 가장 높은 점수를 얻었을 때 그 점수를 구하는 문제이다.

 

먼저 점수를 가장 우선적으로 정렬하고, 점수가 같다면 날짜가 빠른게 더 우선하도록 정렬을 한다. 날짜를 기준으로 하지 않는 이유는

d-1, 1

d-2, 2

d-3, 100

d-3, 100 이 있을 때, d-1, d-2, d-3을 푸는것보다 d-2, d-3, d-3을 푸는게 더 이득이기 때문에 날짜가 아니라 점수를 우선적으로 정렬하는 것이다. 이후 점수가 같으면 날짜가 더 빠른걸 우선하게 하면된다.

 

1. 모든 숙제들중 가장 늦게 풀수있는 숙제의 d-day 만큼의 숙제를 풀 날짜에 해당하는 배열을 만들어준다.
2. 정렬된 숙제들에 대해서 우선순위대로 하나씩 숙제를 뽑아준다.
3. 뽑은 숙제의 D-Day ~ 1일까지 배열을 확인하면서 배열의 값이 초기값 0이라면 (즉, 자신이 그날 숙제를 풀 수 있다면) 배열[그날]에 해당 숙제의 점수를 넣는다. (해당 숙제를 그날 풀게 한다.)
   • 숙제의 d-day가 D라면 D날 풀수있는지부터 ~ 1일날 풀수 있는지 까지 모두 확인한다.
   • 우선순위 큐에서 뽑는 순서가 가장 우선되는 숙제들이므로 날짜가 비어있다면 바로 풀게하면 되는 것이다.
4. 배열의 1~마지막날 내에 들어있는 값이 그날 푼 숙제의 점수들이므로 모두 더해서 반환한다.

🐢코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    static int N;
    static int LAST;
    static PriorityQueue<subject> pq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        pq = new PriorityQueue<>((s1, s2) -> {
            if (s1.point == s2.point) return Integer.compare(s1.dday, s2.dday);
            else return Integer.compare(s2.point, s1.point);
        });
        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int dday = Integer.parseInt(input[0]);
            int point = Integer.parseInt(input[1]);
            LAST = Math.max(dday, LAST);
            pq.add(new subject(dday, point));
        }
        doSubject();
    }

    private static void doSubject() {
        int[] days = new int[LAST + 1];
        Arrays.fill(days, 0);

        while (!pq.isEmpty()) {
            subject nowHw = pq.poll();

            for (int day = nowHw.dday; day >= 1; day--) {
                if (days[day] == 0) { // 문제를 풀수있는 날
                    days[day] = nowHw.point; // 풀게해준다
                    break; // 다음문제 확인
                }
            }
        }

        int sum = 0;
        for (int i = 1; i <= LAST; i++)
            sum += days[i];
        System.out.println(sum);
    }

    private static class subject {
        int dday, point;

        public subject(int dday, int point) {
            this.dday = dday;
            this.point = point;
        }
    }
}