[BaekJoon] 2109 순회강연 (Java)

1.  문제 링크

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

2.  문제

요약

• 한 저명한 학자에게 n개의 대학에서 강연 요청을 해 왔는데, 각 대학에서는 d일 안에 와서 강연을 해주면 p만큼의 강연료를 지불하겠다고 알려왔습니다.
• 각 대학에서 제시하는 d와 p값은 서로 다를 수 있습니다.
• 학자는 강연의 특성상, 하루에 최대 한 곳에서만 강연을 할 수 있는데, d와 p를 바탕으로 가장 많은 돈을 벌 수 있도록 순회강연을 하려 합니다.
• n, d, p가 주어졌을 때, 최대로 벌 수 있는 돈을 구하는 문제입니다.
• 입력: 첫 번째 줄에 0보다 크거나 같고 10,000보다 작거나 같은 강연 요청을 해온 대학의 개수 n이 주어지고 두 번째 줄부터 n개의 줄에 각 대학에서 제시한 p값과 d값이 주어집니다.
  • d는 1 이상 10,000 이하이고, p는 1 이상, 10,000 이하입니다.
• 출력: 첫 번째 줄에 최대로 벌 수 있는 돈을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    // 강연 클래스 생성
    // 강연 데드라인 오름차순으로, 그게 같다면 강연비 내림차순으로 정렬하도록 함
    // PriorityQueue에 강연들을 넣음
    // 새로운 PriorityQueue를 생성한 다음, 거기에 처음 PriorityQueue에서 하나씩 빼서 넣음
    // 만약 현재 데드라인보다 새로운 PriorityQueue에 있는 값의 개수가 더 많다면
    //  데드라인 개수만큼으로 줄임
    // 마지막에 남은 수들을 모두 더함

    static int n;
    static PriorityQueue<Lecture> lectures;

    static void input() {
        Reader scanner = new Reader();

        n = scanner.nextInt();
        lectures = new PriorityQueue<>();

        for(int lecture = 0; lecture < n; lecture++) {
            int pay = scanner.nextInt(), deadline = scanner.nextInt();
            lectures.offer(new Lecture(deadline, pay));
        }
    }

    static void solution() {
        PriorityQueue<Integer> pays = new PriorityQueue<>();

        for(int idx = 0; idx < n; idx++) {
            Lecture lecture = lectures.poll();
            pays.offer(lecture.pay);

            while(!pays.isEmpty() && lecture.deadline < pays.size())
                pays.poll();
        }

        int maxPay = 0;
        while(!pays.isEmpty())
            maxPay += pays.poll();

        System.out.println(maxPay);
    }

    static class Lecture implements Comparable<Lecture> {
        int deadline, pay;

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

        @Override
        public int compareTo(Lecture l) {
            if(this.deadline != l.deadline) return this.deadline - l.deadline;
            return l.pay - this.pay;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 강연을 표현하기 위해 Lecture 클래스를 정의합니다.
  • 강연 기한을 나타내는 필드 deadline과 강연료를 나타내는 필드 pay를 멤버로 가집니다.
  • 이후에 PriorityQueue에 Lecture 객체들을 넣어줄 것인데, 이 때 강연 기한에 대해 오름차순으로 만약 같다면 강연료의 내림차순으로 정렬해줄 수 있도록 Comparable 인터페이스를 구현합니다.

• 주어진 강연들에 대한 정보를 PriorityQueue에 넣습니다.
• 이후에 강연료들을 PriorityQueue에 담을 것이기 때문에 PriorityQueue를 하나 더 생성합니다. 이 PriorityQueue는 강연료를 오름차순으로 정렬합니다.
• PriorityQueue에서 강연 정보를 하나씩 뽑아서 해당 강의의 강연료를 또다른 PriorityQueue에 넣습니다.
• 그리고 강연료를 넣는 PriorityQueue가 비워지거나 현재 PriorityQueue에서 뽑은 강연 정보의 강연 기한이 강연료를 담은 PriorityQueue에 있는 요소의 개수보다 작아지기 전까지 강연료를 담은 PriorityQueue에서 요소를 하나씩 뺍니다.
  • 위 작업을 하는 이유는
    • 강연 정보를 강연 기한의 오름차순으로 정렬했기 때문에 강연 기한은 PriorityQueue에서 강연 정보를 뽑을 때마다 증가합니다.
    • 그런데 강연은 하루에 하나만 진행 가능하므로 강연 기한보다 더 많은 강연을 진행할 수 없습니다. 그러므로 강연료를 담은 PriorityQueue에는 강연 기한보다 작거나 같은 요소의 개수가 존재해야합니다.
    • 또한, 강연 기한이 같다면 강연료 기준 내림차순으로 정렬했기 때문에 강연료를 담은 PriorityQueue에는 최대로 벌 수 있는 경우에 진행하는 행사들의 강연료가 들어있습니다.
• 강연료를 담은 PriorityQueue에 있는 요소들을 모두 더하면 문제의 답이 됩니다.