[백준 15486][JAVA] 퇴사 2

 

가장 끝 날짜부터 첫 날짜로 오면서 dp를 수행했다.

 

dp[i]의 의미는 끝 날짜부터 i 날짜까지 얻을 수 있는 최대 이익이다.

 

dp[i]의 값은 다음 두 가지 경우를 고려해야 한다.

 

1. i번째 날짜에 해당하는 상담을 진행한다.
2. i번째 날짜에 해당하는 상담을 진행하지 않는다.

두 경우 중 큰 값을 골라야 한다.

 

1번을 생각해보자.

 

해당 날짜에 상담을 진행할 경우 그 상담으로 받을 수 있는 금액과 그 상담이 끝난 날짜 이후부터 얻을 수 있는 최대 이익을 더하면 최대 이익이 된다.

 

2번을 생각해보자.

 

해당 날짜에 상담을 진행하지 않을 경우 그 날짜 이후부터 상담으로 얻을 수 있는 최대 이익이 해당 날짜의 최대 이익이 된다.

 

두 경우 중 더 큰 값이 최대 이익이 된다.

 

여기서 중요한 점은 특정 날짜 이후부터 상담으로 얻을 수 있는 최대 이익을 계속 저장해야 한다는 점이다.

 

만약 저장하지 않는다면 특정 날짜 이후부터 끝 날짜까지 모두 순회를 해야 하고 시간 초과가 발생하게 된다.

 

즉 dp[i]의 값을 구할 때는 dp[i+1]의 값과 dp[i+P[i]] 중 큰 값을 고르면 된다.

 

그런데 여기서 제약 조건이 걸려있다.

 

바로 퇴사 날짜에는 상담을 진행하지 않는다는 조건이다.

 

그래서 단순하게 dp[i]의 값을 바로 d[i+1]과 dp[i+P[i]]와 비교하면 안 된다.

 

가장 먼저 dp[i+1]을 저장한 다음 dp[i+P[i]]의 값과 비교해야 한다.

 

해당 날짜에 상담을 진행하기로 결정했을 때 끝 날짜가 퇴사 날짜 이후가 될 수 있지만 해당 날짜에 상담을 진행하지 않기로 결정했을 때는 그렇지 않기 때문이다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] times = new int[n + 2];
        int[] prices = new int[n + 2];
        int[] dp = new int[n + 2];

        StringTokenizer st;
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            times[i] = Integer.parseInt(st.nextToken());
            prices[i] = Integer.parseInt(st.nextToken());
        }

        // DP 역순 탐색
        for (int i = n; i > 0; i--) {
            // 일단 다음 날의 최대 이익을 현재에 반영
            dp[i] = dp[i + 1];

            int end = i + times[i];
            if (end <= n + 1) {
                dp[i] = Math.max(dp[i], dp[end] + prices[i]);
            }
        }

        bw.write(String.valueOf(dp[1]));
        bw.close();
    }
}