백준 2579. 계단 오르기

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

2579번: 계단 오르기

'''
한번에 계단 +1 or +2
연속된 세 계단 밟으면 안됨(+1+1+1 +2+2+2 x)
마지막 도착 계단은 반드시 밟아야 됨 -> 그럼 마지막 칸에서 처음으로 가는 걸 생각해보면?
점수의 최댓값

사고 방식(탑다운): 어디에서 올라왔을까? 한칸 전? 두칸 전?
'''

import sys
input = sys.stdin.readline
n=int(input())
s=[int(input()) for _ in range(n)]
dp=[0]*(n)
if len(s)<=2: # 계단이 2개 이하일 경우는 한칸깡총+한칸깡총으로 고정
    print(sum(s))
else:
    dp[0]=s[0] # 첫 번째 계단(고정)
    dp[1]=s[0]+s[1] # 두 번째 계단(고정)
    for i in range(2,n): # 세번째 계단부터 최댓값 판단해줌
        dp[i]=max(dp[i-3]+s[i-1]+s[i], dp[i-2]+s[i]) # 직전에서(두칸깡총+한칸깡총) 올라옴 vs 두칸전에서(두칸깡총) 올라옴 -> 이렇게 하면 세칸 연속으로 올라올 수가 없음
    print(dp[-1]) # 시작칸 도착했을 경우 누적된 최대점수

탑다운/바텀업을 적극 이용

고정된 값은 미리 넣어두고

패턴을 구해서 점화식을 구해보자!