2579. 계단 오르기

2579. 계단 오르기

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

---

문제의 요점은 연속해서 계단 3개를 밟을 수 없다는 것이다. 작은 단위로 계단이 3개 있을 때를 가정하자면 다음과 같다.

1번 계단 -> 3번 계단 과 1번 계단 -> 3번 계단을 밟는 것 중 최대 값이 3번째 계단에 다다랐을 때의 최대 값이 되는 것이다. (문제에서는 무조건 마지막 계단을 밟아야 한다.)

계단이 4개 있을 때로 문제를 늘리면 

1. 1번 계단 -> 3번 계단 -> 4번 계단 (dp[1] + 계단[3] + 계단[4])

2. 1번 계단 -> 2번 계단 -> 4번 계단 (dp[2] + 계단[4])

왜 1번 계단 이 dp[1]이 되고 1번 계단 -> 2번 계단이 dp[2]가 되는지는, 계단 수를 늘려서 그려보면 이해할 수 있을 것이다.

import java.util.Scanner;

public class Main {

    public int problem2579(int[] stairs) {
        if (stairs.length == 1) {
            return stairs[0];
        } else if (stairs.length == 2) {
            return stairs[0] + stairs[1];
        }

        int[] dp = new int[stairs.length];
        dp[0] = stairs[0];
        dp[1] = stairs[0] + stairs[1];
        dp[2] = Math.max(dp[0] + stairs[2], stairs[1] + stairs[2]);

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

    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc = new Scanner(System.in);
        int stairCount = sc.nextInt();
        int[] stairs = new int[stairCount];
        for (int i = 0; i < stairCount; ++i) {
            stairs[i] = sc.nextInt();
        }
        System.out.println(main.problem2579(stairs));
    }
}