[백준 2579][DP][파이썬] 계단오르기 - 풀이 및 답안

 

문제

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

 

풀이

핵심포인트: 항이 모두 자연수로 이루어졌기에 +2 칸 +2칸 이동은 최적해(최댓값)을 가질 수 없다.
(직관) a_n이 최댓값을 가지기 위해서는 a_n번째 항에 대하여 (X,O O) 1+2 혹은 2+1 (O,X, O) 를 반드시 만족한다.

 

5번째 항까지 구해보면 점화식이 어떻게 되는지 직관적으로 알 수 있다.

 

정답 코드

import sys
input=sys.stdin.readline

N=int(input())

arr=[0]
dp = [0 for _ in range(N+1)]

for _ in range(N):
    arr.append(int(input()))


if N==1:
    print(arr[1])

else:
    #Boundary Condition
    dp[1] = arr[1]
    dp[2] = arr[1] + arr[2]

    #점화식 구현
    for k in range(3,N+1):
        dp[k] = max(dp[k-3] + arr[k-1], dp[k-2]) + arr[k]

    print(dp[N])