백준 - 계단 오르기 ( Java )

 

계단을 연속해서 3개 밟을 수 없고 , 2칸 밟고 1칸 띄고 ,1칸 밟고 2칸 띄고 하는 식으로 생각해야 된다. 

public class 계단오르기 {

    static Integer dp[];
    static int arr[];

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine());

        dp = new Integer[N + 1];
        arr = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }

        dp[0] = arr[0];
        dp[1] = arr[1];

        if (N > 2) {
            dp[2] = arr[1] + arr[2];
        }
        System.out.println(find(N));
    }

    static int find(int N) {

        if (dp[N] == null) {
            dp[N] = Math.max(find(N - 1), find(N - 3) + arr[N - 1]) + arr[N];
        }
        return dp[N];
    }

}