BOJ 2109 순회강연

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

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

---

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

---

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

---

예제 입력 1

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

예제 출력 1

185

---

코드

어제 풀었던 BOJ 13904 과제와 매우 유사한 문제이다.

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

public class Main {
    static class Lecture implements Comparable<Lecture> {
        int price, deadline;

        public Lecture(int price, int deadline) {
            this.price = price;
            this.deadline = deadline;
        }

        @Override
        public int compareTo(Lecture o) {
            return deadline - o.deadline;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력받은 강연 중 마감일이 이른 강연부터 뽑기 위한 우선순위 큐
        PriorityQueue<Lecture> 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 Lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

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

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