백준 14501번 - 퇴사

14501번: 퇴사

 

1. 문제

오늘 부터 N + 1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 적절히 상담을 잡아, 최대 수익을 출력 해야 하는 문제 입니다. 

예시로 주어진 입력 값인데요, Ti = 는 상담 기간, Pi = 상담을 해줌으로써 얻을수 있는 수익 입니다. 예를 들어, 1일에 상담을 하면 2, 3일은 상담을 할수 없고, 10의 수익을 얻을수 있습니다. 이때, 최대 수익을 출력 하시오.

 

 

2. 접근

1. 다이나믹 프로그래밍(dp)를 통해서 접근 할 수 있습니다.

2. 현재 상담 일자의 수익(p[i]) + 현재 상담을 진행 한 후, 부터 얻을 수 있는 최대 수익(t[i] + i)

3. 위와 같은 점화식을 떠올수 있습니다.

4. dp[i] = Max(p[i] + dp[t[i] + i], maxValue)

5. dp[i]는 i번째 부터 마지막 날(n - 1)까지 얻을수 있는 최대 수익 입니다.

6. maxValue는 현재 까지의 최대 수익금 입니다.

7. 그런데, 이 문제는 마지막 날짜 부터 계산 해주는것이 편합니다.

8. dp[n - 1] 부터 계산해 주는것이 편합니다.

9. t[i] + i > n 라면, 문제의 주인공은 퇴사 후 이므로 수익을 낼수 없습니다.

 

 

3. 이해를 돕기 위해서

먼저, 위와 같이 maxValue를 생각 하지 않고, dp[i]를 구하여 봅니다.

 

 

그리고, max 연산을 이용해서, maxValue 까지 생각해 보시면, 쉽게 이해가 갈것 입니다. 그럼, 위의 예시만 봐서는 maxValue를 굳이 써야 되나? 라는 생각이 들수 있습니다. 백준의 마지막 입력4, 출력4를 대입해서 풀어보시면, maxValue가 꼭 필요 합니다. 그렇지 않으면, 최대 수익이 아니라, 기간 순에 따른 수익금이 출력 됩니다.

 

 

4. java 소스

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

public class BOJ14501 {
    // https://www.acmicpc.net/problem/14501
    // 퇴사
    public static void main(String[] args) throws IOException {
        // 뒤쪽 부터 계산
        // dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
        // maxValue = 뒤쪽 부터 계산 했을 때, 현재 까지의 최대 상담 금액
        // 점화식 dp[i] = max(p[i] + dp[t[i] + i], maxValue)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // n은 전체 일수, maxValue 뒤쪽 부터 계산 했을때, 현재 까지의 최대 금액
        int n, maxValue;
        // dp 점화식, p 이익, t 기간
        int[] dp, p, t;

        n = Integer.parseInt(st.nextToken());
        maxValue = Integer.MIN_VALUE;
        dp = new int[n + 1];
        p = new int[n];
        t = new int[n];

        try {
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                t[i] = Integer.parseInt(st.nextToken());
                p[i] = Integer.parseInt(st.nextToken());
            }
        } finally {
            br.close();
        }

        // 뒤쪽부터 계산
        for (int i = n - 1; i >= 0; i--) {
            if (t[i] + i <= n) {
                dp[i] = Math.max(p[i] + dp[t[i] + i], maxValue);
                maxValue = dp[i];
            } else {
                dp[i] = maxValue;
            }
        }

        final int ERROR = -1;
        maxValue = Arrays.stream(dp)
                .max()
                .orElse(ERROR);
        System.out.println(maxValue);
    }
}

 

위 소스 코드는 반복문으로 이용해서 작은 문제(dp[n - 1]) 부터 해결하여, 작은 문제를 활용 하여, 큰 문제(dp[0])를 해결 하였습니다. 위 예시에서 '1일 부터 수익' = '1일 수익' + '4일 수익' + '5일 수익' 구한것 처럼, '1일 부터 수익'은 "큰 문제", '4일 수익', '5일 수익'은 작은 문제의 해당 합니다. 이와 같은 다이나믹 프로그래밍의 보텀업 방식 입니다. 반대로, 재귀 함수를 이용해서 큰 문제를 해결 하기 위해 작은 문제를 호출 하는 '탑 다운 방식'도 있습니다.

 

 

5. 다이나믹 프로그래밍 접근

1. 큰 문제를 작은 문제로 나눌 수 있습니다.

2. 작은 문제에서 구한 답을 이용하여 큰 문제도 해결 할수 있습니다.