백준 2579번 계단오르기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ClimbingStairs {
    static int[] dp;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        dp = new int[N+1];
        for (int i = 1; i < N+1; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(recur(N));
    }
    public static int recur(int n){
        if(n==0){
            return 0;
        }
        else if(n==1){
            dp[1] = arr[1];
        }
        else if(n==2){
            dp[2] = arr[1]+arr[2];
        }
        else if(dp[n]==0){
            dp[n] = Math.max(recur(n-3)+arr[n-1],recur(n-2)) + arr[n];
        }
        return dp[n];
    }
}

풀이방법

2가지 경우의 수중 더 큰값을 dp배열에 메모이제이션하면서 진행한다.
이때 n-1은 메모이제이션 하지 않고, arr[n-1]을 그대로 더해준다.
이유는 n-1을 메모이제이션 하면, dp[5],dp[4],dp[3]...등 이전 계단을 밟았는지를 알수가 없다.
📢따라서 (recur(n-3)+arr[n-1])을 한 세트로 생각하고 설계한다.

후기

dp는 핵심 포인트를 파악하는게 너무 어려운것 같다.