[JAVA] 백준 퇴사

dfs를 사용하려다가 탐색을 끝내는게 안됐다.

 

그래서 알아보니 dp를 사용하는 문제였다.

 

뒤에서부터 생각해보자.

https://bcp0109.tistory.com/8

최대한 많은금액 = 1일 금액 + 4일부터 받을 수 있는 최대 금액

= P[1] + dp[4]

하지만, 2일금액이나 3일 금액을 선택하는 경우도 생각해보자

 

dp[7] = MAX(P[7] + dp[7+2], dp[8]) => 7일금액+9일부터 받을수있는최대금액 vs 8일부터 받을수있는 최대금액

...(if (day <= n + 1){ //퇴사일까지.)

dp[7] = MAX(P[5] + dp[5+2], dp[6]) => 7일금액+7일부터 받을수있는최대금액 vs 6일부터 받을수있는 최대금액

...

dp[2] = MAX(P[2] + dp[6], dp[3]) => 2일금액+6일부터 받을수있는최대금액 vs 3일부터 받을수있는 최대금액

dp[1] = MAX(P[1] + dp[4], dp[2]) => 1일금액+4일부터 받을수있는최대금액 vs 2일부터 받을수있는 최대금액

 

 

점화식은 아래와 같다.

dp[i] = MAX(P[i] + dp[i+T[i]], dp[i+1])

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] time = new int[n+2];
        int[] pay = new int[n+2];
        int[] dp = new int[n+2];

        for (int i = 1; i <=n; i++) {//0릉 비워놓고 1~n까지
            time[i] = sc.nextInt();
            pay[i] = sc.nextInt();
        }

        for(int i=n; i>0; i--) {//끝에서부터 내려감
            int day = i + time[i];

            if (day <= n + 1) //퇴사일까지.
                dp[i] = Math.max(pay[i] + dp[day], dp[i + 1]);
            else //퇴사일초과
                dp[i] = dp[i + 1];

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