문제링크

풀이

문제에 적힌 세가지 조건을 만족하는 n번째 계단에 도달할 수 있는 방법을 점화식으로 세운다.
1. 두 계단 아래에서 올라오기: n-2 → n
2. 한 계단 아래에서 올라오기: 이 경우에는 한가지 더 생각을 해야한다. 2번 조건인 "연속된 세 개의 계단을 모두 밟아서는 안 된다."를 고려하면, n-3 → n-1 → n 이 된다.

두가지 방식을 종합하여 점화식을 세우면,
dp[n] = Math.max(dp[n-2], dp[n-3] + arr[n-1]) + arr[n];
이 된다.

코드

package BOJ;

import java.io.*;

public class sol2579 {
    static int n;
    static int[] arr;
    static int[] dp;

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

        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        dp[1] = arr[1];

        if (n >= 2) {
            dp[2] = arr[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]);
    }
}