[백준] Python 2579번 계단 오르기 실버3 - DP

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

접근 방법

1. 마지막 계단과 N-1번째 계단 or N-2번째 계단을 더한 값 중 큰 것을 고르면 된다.
2. N-1번째 계단을 고르면 N-3번째 계단을 밟았다는 의미이다.

풀이

N = int(input())
stairs = [int(input()) for _ in range(N)]
dp = [0] * N

if N <= 2: # 2이하인 경우는 모두 더하면 된다
    print(sum(stairs))
else:
    dp[0] = stairs[0] # 첫 번째 계단
    dp[1] = max(stairs[0] + stairs[1], stairs[1]) # 두 번째 계단

    for i in range(2, N):
        dp[i] = stairs[i] + max(dp[i-3] + stairs[i-1], dp[i - 2])

    print(dp[-1])