[백준] 2579 계단 오르기 [java]

문제

https://www.acmicpc.net/problem/2579

풀이 방법

1 or 2 계단씩 올라갈 수 있다. 중요한 것은, 연속으로 세 계단을 올라가지 못한다는 것이다.
완전탐색으로 모든 경우의 수를 따지면 좋겠지만, 시간 초과가 난다. DP로 해결해야 한다.

세 계단을 연속으로 올라가지 않고 n에 도달하는 방법은 이 두 가지 뿐이다.
점화식은

dp[n] = Math.max(dp[n - 2], dp[n - 3] + arr[n - 1]) + arr[n]

이다

코드

import java.util.Scanner;

// 한개 또는 두개 이동, 연속 세개 안됨
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] arr = new int[size + 1];
        int[] dp = new int[size + 1];
        for(int i = 1; i <= size; i++){
            arr[i] = scanner.nextInt();
        }

        dp[1] = arr[1];
        if(size >= 2){
            dp[2] = arr[1] + arr[2];
        }

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

        System.out.println(dp[size]);
    }
}