[백준] 온라인 저지 14501번 : 퇴사 준비하기(Java), DP

 

마찬가지로 점화식을 세운 후 진행한다.

날짜를 거꾸로 계산해야 해서 조금 헷갈렸던 문제..

 

 

문제 풀이

import java.util.Scanner;

public class P14501_퇴사준비하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int time[] = new int[N+1];
        int pay[] = new int[N+1];
        int dp[] = new int[N+2];

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

        for(int i=N; i>0; i--) {
            if(i + time[i] > N+1) {
                // 퇴사 이후에는 불가능
                dp[i] = dp[i+1];
            } else {
                dp[i] = Math.max(pay[i] + dp[i + time[i]], dp[i+1]);
            }
        }
        System.out.println(dp[1]);
    }
}