백준 Java 2579_계단 오르기

• 두 계단 전의 경우와(N-2) 와 직전 계단을 밟고(N-1) 그 이전에는 두 계단 이전의 경우(N-3)에서 연속되지 않는 위치인 N-2와 N-3에 대해서만 재귀호출을 해주어야 한다.
• 두 칸 전(i - 2)의 '메모이제이션 값'과 첫 칸 전(i - 1)의 값 + 셋 째칸 전(i - 3)의 '메모이제이션 값'
  중 큰 값을 현재 i 계단의 값과 합하여 DP배열에 저장(Memoization)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 한번에 한계단 씩 or 두 계단씩 가능
        //연속된 세개 불가
        //마지막 반드시 밟아야한다.
        int  N = Integer.parseInt(br.readLine());
        int[] arr = new int[N +1];
        for (int i = 1; i < N+1 ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        int[] dp = new int[N + 1];
        dp[1] = arr[1];
        if(N >=2 )
        dp[2] = dp[1] + arr[2];

        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i - 2], dp[i - 3] + arr[i-1]) +arr[i];
        }
        System.out.println(dp[N]);
    }

}