문제

계단 오르기

풀이

DP 문제 이므로 점화식을 세우는게 가장 중요합니다. 조건이 주어졌으므로 조건을 하나하나 살펴보겠습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

0 번째 계단을 밟은 경우 , dp[0] = arr[0] 0번째 계단을 밟을 수 있음
1 번째 계단을 밟은 경우 , dp[1] = arr[1] + arr[0] 또는 arr[1] => 0,1 번계단을 밟거나 1번계단을 밟을 수 있음
2 번째 계단을 밟은 경우 , dp[2] = arr[1] + arr[2] 또는 arr[0] + arr[2] => 1,2 번 계단을 밟거나 0,2 번 계단을 밟을 수 있음
3 번째 계단을 밟은 경우, dp[3] = arr[0] + arr[2] + arr[3] 또는 arr[0] + arr[1] + arr[3] => 0,2,3 번 계단을 밟거나 0,1,3 계단을 밟을 수 있음

밟은 수 있은 횟수중에 가장 많은 점수를 얻을 수 있는 경우를 dp 배열에 저정하면 된다
3번째부터 일정한 점화식이 등장하는데,

규칙을 정하면 다음과 같다

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

		int[] dp = new int[n];
        dp[0] = arr[0];
        if (n > 1) {
            dp[1] = Math.max(arr[1], arr[0] + arr[1]);
        }
        if (n > 2) {
            dp[2] = Math.max(arr[1] + arr[2], arr[0] + arr[2]);
            for (int i = 3; i < n; i++) {
                dp[i] = Math.max(arr[i] + dp[i - 2], arr[i - 1] + arr[i] + dp[i - 3]);
            }
        }
        System.out.println(dp[n - 1]);

전체 코드

전체 코드