[알고리즘] 백준 > #13904. 과제

문제링크

벡준 #13904. 과제

풀이방법

이 풀이방법의 아이디어는 각 날에 풀 문제를 고르자 이다. 그럼 그 날 풀 수 있는 문제들을 알고 있어야 하는데 이를 위해서는 마지막날 부터 진행하는게 수월하다고 생각했다. 왜냐하면 마지막날부터 진행하면 지나온 날과 해당 날이 마감일인 과제들을 자료구조에 넣으면 쉽게 구할 수 있기 때문이다! 최대점수를 얻기 위해 그 날 풀 수 있는 문제 중 점수가 가장 큰 것을 골라 풀도록 했다. 최대점수를 쉽게 구하기 위해 우선순위큐를 이용했다. 또, 각 날이 마감일인 숙제들을 쉽게 관리하기 위해 LinkedList로 이루어진 배열을 이용했다. 그 날 과제가 몇개가 될 지 모르고, 순서대로 접근하기 때문에 LinkedList가 적합하다고 생각했다.

코드

class Solution13904 {
    private LinkedList<Integer>[] homeworks;
    private int lastDue;

    Solution13904(LinkedList<Integer>[] homeworks, int lastDue) {
        this.homeworks = homeworks;
        this.lastDue = lastDue;
    }

    int getMaxScore() {
        int score = 0;

        PriorityQueue<Integer> homeworkQ = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = lastDue; i > 0; i--) {
            for (Integer homework : homeworks[i]) homeworkQ.offer(homework);
            if (!homeworkQ.isEmpty()) score += homeworkQ.poll();
        }

        return score;
    }
}