[알고리즘] 백준 2579 계단오르기

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

2579번: 계단 오르기

import java.util.Scanner;

public class BJ_2579 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] stair = new int[n + 1];
        int[] dp = new int[n + 1];

        for (int i = 1; i < n + 1; i++) {
            stair[i] = scan.nextInt();
        }

        if (n >= 1) {
            dp[1] = stair[1];
        }

        if (n >= 2) {
            dp[2] = stair[1] + stair[2];
        }

        if (n >= 3) {
            dp[3] = Integer.max(stair[1] + stair[3], stair[2] + stair[3]);
        }

        if (n >= 4) {
            for (int i = 4; i < n + 1; i++) {
                dp[i] = Integer.max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
            }
        }

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

 

앞서 풀었던 포도주 문제와 비슷한 유형이다.

 

연속해서 계단을 세개를 밟을 수 없고 마지막 계단은 꼭 밟아야 하기 때문에 경우의 수는 아래와 같다.

 

■XOO -> dp[i - 3] + stair[i - 1] + stair[i]

■OXO -> dp[i - 2] + stair[i]

 

따라서 dp[i]의 값은 위 두개 경우중 큰 값이 된다.