[백준] 온라인 저지 14586번 : 퇴사 2(Java), DP

문제 풀이

import java.util.*;

public class P026_BOJ거리구하기 {
    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];

        // 점화식
        // dp[N] : N일까지 일하는데 받는 최대 비용

        for(int i=1; i<N+1; 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(dp[i+1], pay[i] + dp[time[i] + i]);
            }
        }

        System.out.println(dp[1]);
    }
}