[2579] 계단 오르기

처음에 점화식 쉽게 생각해서

d[i-1] + s[i] 전칸까지의 합이랑 d[i-2] + s[i] 전전칸 까지의 합 중에 최댓값 구하면 되는게 아닌가 생각했는데

그러면 무조건 모든 칸을 밟게 됨

 

규칙에선 3번 연속 밟으면 안 된다고 했음

d[i-2]+stair[i] 한칸을 띄운 버전이랑 d[i-3] 두칸 전까지의 합에 한칸을 띄우고 stair[i-1] 이전칸의 합과 stair[i]현재까지의 합을 더해야 한다

import sys

input = sys.stdin.readline

stair = [0] * 301

n = int(input())

for i in range(1, n+1):

    t = int(input())

    stair[i] = t

d = [0] * 301

d[1] = stair[1]

d[2] = stair[1] + stair[2]

d[3] =  max(d[1]+stair[3], d[0]+stair[2]+stair[3])

for i in range(2, n+1):

    d[i] = max(d[i-2]+stair[i], d[i-3]+stair[i-1]+stair[i])

print(d[n])