[Python] 계단 오르기 - 백준 (DP)

해당 글은 백준 2579번 문제 '계단 오르기'를 다룬다.

문제

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

2579번: 계단 오르기

 

설명

해당 문제는 동적 계획법 알고리즘으로 풀 수 있는 문제이다.

마지막 n번째 계단은 반드시 밟아야 하므로, 마지막 n번째 계단을 밟을때

1) n-1번째 계단을 밟지 않는 경우, n-2번째 계단을 밟는다.

2) n-1번째 계단을 밟는 경우, n-2번째 계단을 밟지 않는다.

즉, 점화식은 아래와 같이 표현된다.

dp[i] = max(stairs[i]+dp[i-2], stairs[i]+stairs[i-1]+dp[i-3])

 

코드

n = int(input())
stairs = []
for i in range(n):
    stairs.append(int(input()))

dp = [0]*n
dp[0] = stairs[0]
if n > 1:
    dp[1] = max(stairs[1]+dp[0], stairs[1])
if n > 2:
    dp[2] = max(stairs[2]+dp[0], stairs[2]+stairs[1])

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

print(dp[n-1])