[BOJ] 14501. 퇴사

 

문제

 

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

 

 

다음 문제에서 목표로 하는 최대 수익을 얻으려면 모든 가능한 선택지를 비교하고, 가장 높은 수익을 선택해야 한다.

아래 문제를 보면, i일 이후에도 얻을 수 있는 최대 수익을 대략적으로 계산할 수 있다. 이러한 특징을 기반으로 현재를 최적화하는 방식에 적합한 DP 방식으로 풀이해보았다.

 

 

 

점화식 세우기

 

i번째 날에서 선택될 수 있는 결정은 두 가지로 구분될 수 있다.

 

오늘 시작되는 상담을 했을 때, 퇴사일까지 끝나지 않는 경우 (상담하지 못한다)

오늘 시작되는 상담을 했을 때, 퇴사일 안에 끝나는 경우 (상담한다)

 

 

 

i일에 상담 가능한 경우의 기준

• 상담이 끝나는 날인 i + T[i] -1 일이 N 이하여야 한다.
• 즉, i + T[i] > N + 1 인 경우에는 상담을 못한다.

 

 

i일에 상담하지 못하는 경우

• i일에 상담을 하지 않으면 수익은 0
• i+1 일에는 최적의 수익을 얻을 수 있는 상황이 됨.
• 즉, 이 경우의 최대 수익 = D[i+1]이 됨.

 

 

상담하는 경우

• i일부터 상담하면, P[i]의 수익을 얻고, T[i]일 동안 다른 상담이 불가능 
• i + T[i]일부터 남은 기간에 대해 최대 수익 D[i+T[i]]을 추가적으로 계산해야 함. (상담이 끝난 이후 남은 기간에 대한 최대 수익을 나타냄)
• 그러므로 i일에 얻는 수익 P[i]를 더함
• 이 경우의 최대 수익 = P[i] + D[i+T[i]] 가 됨.

 

최대 수익 비교 선택

 

상담을 하지 않는 경우와 상담을 하는 경우 중 최대 수익을 비교한다.

위 두 경우 중, 더 큰 수익이 D[i]에 얻을 수 있는 최대 수익이 됨.

D[i] = max(D[i+1], P[i]+D[i + T[i]])

 

 

 

 

풀이

 

상담하는 경우의

• i + T[i]일부터 남은 기간에 대해 최대 수익 D[i+T[i]]을 추가적으로 계산해야 함. (상담이 끝난 이후 남은 기간에 대한 최대 수익을 나타냄)
• i일에 얻는 수익 P[i]를 더함
• 최대 수익 = P[i] + D[i+T[i]]

 

위 설명이 처음 보면 조금 이해가 어려울 듯 해서 다시 정리해보았다.

(i=5일 때)

D[i + T[i]] : 5~6일까지 상담하는 2일 간을 제외하고, 퇴사까지 남은 기간 동안 얻게 될 최대 수익 => D[7] = 0

P[i] : i일에 상담해서 얻은 수익

 

 

뒤에서부터 역순으로 계산하면 미래의 최적 결과를 미리 알고 있으므로, i일에 대한 최적의 값을 구할 수 있다.

마지막 날은 더 이상 상담을 할 수 있는 미래가 없으므로, 그날 상담을 할지 말지만 구분하면 된다.

이를 기반으로 퇴사 전 마지막 날부터 첫번째 날까지 반복하여 계산한다.

이전 단계의 결과가 이미 계산되어 있으므로, i일을 계산할 때 미래의 최대 수익을 참고하여 최적의 결과를 구할 수 있다.

 

package DP;

import java.util.Scanner;

public class BOJ14501 {
    static int[] T;
    static int[] P;
    static int[] D;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        // 상담을 완료하는데 걸리는 기간
        T = new int[N+1];
        // 상담을 했을 때 받을 수 있는 금액
        P = new int[N+1];
        // i일에 상담했을 때 얻을 수 있는 최대 수익
        D = new int[N+2];

        for (int i=1; i<=N; i++) {
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }

        for (int i=N; i>0; i--) {
            // 상담 가능 기준 : 상담이 끝나는 날인 i + T[i] -1 일이 N 이하여야 한다
            // 오늘 시작되는 상담 했을 때, 퇴사일까지 끝나지 않는 경우
            if (i + T[i] > N+1) {
                D[i] = D[i+1];
            } else {
                // 상담 하거나 하지않은 경우를 비교한 최대값
                // 오늘 시작되는 상담을 했을 때, 퇴사일 안에 끝나는 경우
                D[i] = Math.max(D[i+1], P[i] + D[i +T[i]]);
            }
        }
        System.out.println(D[1]);
    }
}