백준 2109번 : 순회 강연

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

 

저명한 학자가 가장 많은 페이를 받을 수 있도록 도와드려야 합니다. 

 

풀이

 

이 문제가 그리디적인 해결이 가능할까 라고 고민이 될 때가 많습니다. 그때 저 나름에 비법이 있습니다. 비밀인데

 

"선택을 해야하는 과정에서 다른 경우를 배제하고 선택할 수 있으면 그리디"입니다. 네? 그게 그리디 알고리즘의 기본 아니냐고요? 그럼 조금 더 설명을 해보겠습니다

 

이 문제에서, 학자는 돈을 최대한 많이 벌고 싶습니다. 오직 돈. 이러한 욕심을 채우기 위해서는 어떤 강의를 선택해야 할까요? 당연히 돈을 많이 주는 강의를 선택해야 합니다. 그럼 가장 많은 돈을 벌기위한 강의 스케줄을 구성하면서, 가장 페이가 많은 강의를 포기할 수 없습니다. 

 

위 말을 좀 정리해보자면, "남은 강의 중 가장 페이가 높은 강의를 선택" 하면, 가장 높은 페이를 받는 스케줄을 만들 수 있습니다. 

 

그렇다면 이해를 돕기위해 DP와 같이 모든 경우를 확인해야 하는 경우도 한번 생각을 해보겠습니다. 

 

만일 강의가 놀랍게도 시작날과 끝날이 존재하는 정말 긴 강의인 경우로 가정해 보겠습니다. 

 

1번 강의는 1일부터 5일까지 진행되고 3천원을 줍니다.

2번 강의는 1일부터 2일까지 진행되고 2천원을 줍니다.

3번 강의는 3일부터 4일까지 진행되고 2천원을 줍니다. 

 

여기서 앞서 생각한 그리디의 원리로 접근하게 되면 3천 원을 주는 1번 강의를 선택하게 됩니다. 하지만 학자에게는 비밀이지만 사실은 그게 최선이 아닙니다. 

2번과 3번 강의를 선택하면 4천원을 받을 수 있습니다..!

즉 단순히 "가장 페이를 많이주는 강의를 한다"라는 선택의 기준이 정답이 아닌 상황입니다. 이런 경우를 저는 "모든 경우를 다 확인하는 경우"라고 말합니다. 

 

그렇다면 다시 본론으로 돌아와서, 단순히 페이가 높은 강의를 선택하면 문제가 해결 된다는 것을 알았습니다. 

 

하지만 아쉽게도 이 문제의 2번째 포인트가 있습니다. 

 

d일 안에 강의를 해야합니다. 

 

정해진 d일에 강의를 할 수도 있지만 d-1, d-2.. 일에도 강의를 할 수 있습니다. 즉 강의가 선택되었을 때 스케줄에 체크를 해줘야 합니다.

 

저는 이 과정을 Union&Find에서 find 과정을 통해 구현했습니다. 

 

코드

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

public class Num2109순회강연 {
    private static class Work{
        int pay;
        int until;
        Work(int pay, int until){
            this.pay = pay;
            this.until = until;
        }
    }
    static int[] vis;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Work> pq = new PriorityQueue<>(new Comparator<Work>() {
            @Override
            public int compare(Work o1, Work o2) {
                if(o1.pay == o2.pay){
                    return o2.until - o1.until;
                }
                return o2.pay - o1.pay;
            }
        });
        StringTokenizer st;
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int pay = Integer.parseInt(st.nextToken());
            int until = Integer.parseInt(st.nextToken());
            pq.add(new Work(pay,until));
        }
        int ans = 0;
        vis = new int[10_001];
        for(int i=0;i<10_001;i++){
            vis[i] = i;
        }
        while(!pq.isEmpty()){
            Work now = pq.poll();
            int tmp = find(now.until);
            if(tmp !=0){
                vis[tmp] = tmp-1;
                ans += now.pay;
            }
        }
        System.out.println(ans);
    }
    public static int find(int a){
        if(vis[a] == a){
            return a;
        }
        return vis[a] = find(vis[a]);
    }
}