BOJ 13904 과제

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

문제

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

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

---

입력

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

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

---

출력

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

---

예제 입력 1

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

예제 출력 1

185

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Task implements Comparable<Task> {
        int deadline, score;

        public Task(int deadline, int score) {
            this.deadline = deadline;
            this.score = score;
        }

        @Override
        public int compareTo(Task o) {
            return deadline - o.deadline;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력받은 과제 중 마감일이 이른 과제부터 뽑기 위한 우선순위 큐
        PriorityQueue<Task> queue = new PriorityQueue<>();
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            queue.offer(new Task(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // 선택한 과제의 점수 중 가장 낮은 과제의 점수를 뽑기 위한 우선순위 큐
        PriorityQueue<Integer> scores = new PriorityQueue<>();
        while (!queue.isEmpty()) {
            // 입력받은 과제들을 마감일이 이른 순으로 뽑아 검사한다.
            Task check = queue.poll();
            // 만약 검사 중인 과제의 마감일이 scores 큐의 크기보다 작을 경우, 해당 과제 점수를 큐에 추가
            if(scores.size() < check.deadline)
                scores.offer(check.score);
            /**
             * 검사 중인 과제의 마감일이 scores 큐의 크기보다 크고,
             * 검사 중인 과제의 점수가 scores 큐에 있는 가장 낮은 점수보다 클 경우,
             * 큐에서 가장 낮은 점수를 뽑고 검사 중인 과제의 점수를 offer 함
             */
            else if(scores.peek() < check.score) {
                scores.poll();
                scores.offer(check.score);
            }
        }

        int answer = 0;
        while (!scores.isEmpty()) answer += scores.poll();
        System.out.println(answer);
    }
}