[백준/파이썬] 2579번

📍백준 2579 문제

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

코드

import sys
input = sys.stdin.readline

n = int(input())

stair = [0] * 301
for i in range(1, n+1):
    stair[i] = int(input())
dp = [0] * 301
dp[1] = stair[1]
dp[2] = stair[1]+stair[2]
dp[3] = max(stair[1] + stair[3], stair[2] + stair[3])
for i in range(4, n+1):
    dp[i] = max(dp[i-3]+stair[i-1]+stair[i], dp[i-2] + stair[i])
print(dp[n])

풀이

점화식을 이용해서 풀면 된다.
1. 연속해서 올라 온 경우 => dp[i-2] + stair[i]
2. 점프에서 한 단계 넘어 온 경우 => dp[i-3]+stair[i-1]+stair[i]
이 두개의 경우 중 최대인 값을 저장하면 된다.