[JAVA] 백준 (골드3) 2109번 순회강연

링크

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

---

입력 예제

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

---

출력 예제

185

---

풀이

다음과 같이 4개의 강연이 있다고 할 때

[2, 1], [3, 1], [4, 2], [5, 2]

최대로 강연료를 받는 경우는 1일 차, 2일 차에 3번째와, 4번째의 강연을 하여 총 9만큼의 강연료를 받는 경우이다.

이것을 구현하기 위해 우선 Lecture 클래스로 List를 생성하여 강연들의 정보를 저장한다. 그리고 일자를 기준으로 강연의 수를 제한해야 되기 때문에 일자를 기준으로 정렬해준다.

List<Lecture> lectures = new ArrayList<>();
lectures.sort(Comparator.comparingInt(o -> o.day));  //강연 일자를 기준으로 정렬

그리고 lectures를 반복하며 우선순위 큐에 강연의 강연료를 추가한다. 이때 추가되는 강연료는 오름차순으로 정렬되며 추출 시 강연료가 가장 낮은 강연부터 제거된다. 큐의 크기가 강연의 일자보다 커지면 제일 작은 강연료의 강연을 제거해나간다.

PriorityQueue<Integer> pq = new PriorityQueue<>();  //강연료를 오름차순으로 저장

for (Lecture lecture : lectures) {
    pq.add(lecture.pay);
    //가능한 날짜 수를 초과했다면, 강연료가 가장 낮은 강의를 제거
    if (pq.size() > lecture.day) {
        pq.poll();
    }
}

이제 큐에 남은 강연들이 문제 조건에 해당되게 된다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
백준 / 순회강연 / 골드3
https://www.acmicpc.net/problem/2109
 */
public class BOJ_2109 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        List<Lecture> lectures = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            lectures.add(new Lecture(p, d));
        }

        lectures.sort(Comparator.comparingInt(o -> o.day));  //강연을 일자를 기준으로 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>();  //강연료를 오름차순으로 저장

        for (Lecture lecture : lectures) {
            pq.add(lecture.pay);
            //가능한 날짜 수를 초과했다면, 강연료가 가장 낮은 강의를 제거
            if (pq.size() > lecture.day) {
                pq.poll();
            }
        }

        int totalPay = pq.stream()
                .mapToInt(Integer::intValue)
                .sum();

        System.out.println(totalPay);
    }

    static class Lecture {
        int pay, day;

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