[백준] 14501 - 퇴사 (Java)

import java.io.*;

public class No14501_퇴사 {

    static int max=0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int t[] = new int[n+10];
        int p[] = new int[n+10];
        int dp[] = new int[n+10];

        String temp[];

        for (int i = 1; i <= n; i++) {
            temp = br.readLine().split(" ");
            t[i] = Integer.parseInt(temp[0]);
            p[i] = Integer.parseInt(temp[1]);
        }


        for (int i=n;i>0;i--) { //뒤에서부터 검사
            int next = i+ t[i]; //각 상담이 끝나는날
            if (next > n+1 ) {
                dp[i] = dp[i+1];//일할 수 있는 날짜를 넘어가는 경우, skip
            }
            else {
                dp[i] = Math.max(dp[i+1],dp[next]+p[i]);
            }// skip, counsel중에 큰값 리턴
        }
        System.out.println(dp[1]);
    }


}

🎀 놓친 점

• for문을 돌때 뒤에서 부터 검사하는 점

🏆 배운 점

• DP니까 메모이제이션! 메모하면서 최대값 찾기
  dp [i] = dp[i-1] + i 느낌 알기

어렵다,,, 구글링해보니까 DFS로 푼 사람들도 있었다. n이 작기 때문에 DFS로 해도 문제가 없는듯 하였다. 17년도 삼성역량테스트? 문제였다한다...

참고한 블로그 : 여기!