[백준] 2109. 순회강연 (그리디/Java)

[백준] 2109. 순회강연

 

😎 문제 조건

• 각 대학은 d일 안에 와서 강연을 해주면 p만큼 강연료를 지불한다.
• 하루에 최대 한 곳에서만 강연이 가능하다.
• 가장 많은 돈을 벌 수 있도록 스케줄을 짜야 한다.

 

📌 풀이 과정

1. 강연료가 높은 순서대로 정렬하여 하나씩 처리한다.
2. 각 강연은 마감일부터 1일까지 역순으로 탐색하며 가장 늦은 빈 날짜에 배정한다.

 

강연료 기준으로 내림차순 하기

다른 풀이들을 보면 강연료가 같은 경우 마감일까지 정렬 기준으로 고려한 풀이가 많았다.

하지만 실제로는 강연료만으로 정렬해도 정답을 구할 수 있다!

 

그 이유는 뭘까?

 

그리디 알고리즘의 핵심은 "가장 가치 있는 것 = 높은 강연료" 부터 처리하는 것이다.

강연료가 같은 두 강연이 있을 때, 어느 것을 먼저 처리하든 결과적으로 동일한 스케줄이 나온다.

 

예를 들어보자.

강연료가 같은 강연 A(마감일 5일)와 B(마감일 3일)가 있을 때,

• A를 먼저 처리하면 A는 5일에, B는 3일에 배정된다.
• B를 먼저 처리하면 B는 3일에, A는 5일에 배정된다.

두 경우 모두 총 강연료는 동일하다.

즉, 마감일이 다르더라도 강연료가 같다면 어느 것을 먼저 처리하든 최종 결과(최대 강연료 합계)에는 영향을 주지 않는다.

 

✨ 제출 코드

메모리: 21104 KB

시간: 260 ms

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

public class Main {

    static class Lecture{
        int pay;
        int day;

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

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        boolean[] visited = new boolean[10001];
        int answer = 0;

        PriorityQueue<Lecture> pq = new PriorityQueue<>((l1, l2) -> {
            return l2.pay - l1.pay; // 강연료로 내림차순
        });

        for(int i = 0; i < N; i++){
            String[] parts = br.readLine().split(" ");
            int pay = Integer.parseInt(parts[0]);
            int day = Integer.parseInt(parts[1]);
            pq.add(new Lecture(pay, day));
        }

        while(!pq.isEmpty()){
            Lecture tmp = pq.poll();
            for(int i = tmp.day; i > 0; i--){
                if(!visited[i]){
                    visited[i] = true;
                    answer += tmp.pay;
                    break;
                }
            }
        }

        System.out.println(answer);
    }
}