2579번 : 계단 오르기 - Python

문제

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

풀이

계단을 밟을 수 있는 방법은 두가지 이다.

1. 전전꺼를 안밟고, 전꺼 밟고, 밟기 -> A[i-3] + A[i-1] + A[i]
2. 전전꺼를 밝고, 전꺼 안밟고, 밟기 -> A[i-2] + A[i]

코드

from sys import stdin

input = stdin.readline

n = int(input())

array = [int(input()) for i in range(n)]
dp = [0 for i in range(n)]

dp[0] = array[0]

for i in range(1, n):
    if i==1:
        dp[1] = array[1]+array[0]
    elif i==2:
        dp[2] = max(array[2]+dp[0],array[2]+array[1])
    else:
        dp[i] = max(dp[i-2]+array[i], array[i]+array[i-1]+dp[i-3])

print(dp[-1])