[boj] 백준 2579 계단 오르기 python 풀이

문제

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

2579번: 계단 오르기

 

 

문제 풀이

dp, 세번 연속으로 1칸씩 이동하는 경우는 없어야 하므로, dp[i]가 두번째 1칸씩(stairs[i-1] + stairs[i-2]) 이동이라면 dp[i-3]을 더해줘서 무조건 불연속하게 만들기

 

코드

import sys
input = sys.stdin.readline

N = int(input().strip())
stairs = [int(input().strip()) for _ in range(N)]

dp = [0 for _ in range(N)]
dp[0] = stairs[0]
if N > 1:
    dp[1] = stairs[1]+stairs[0]
if N > 2:
    dp[2] = max(stairs[2] + stairs[1], stairs[2] + stairs[0])

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

print(dp[-1])