문제

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

코드

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

print(dp[n-1])

• DP문제
• 최대 300개의 글자를 받으므로 그 공간을 만든다.
• 계단오르기는 앞에서부터가 아닌 끝에서부터 생각한다.
• 현재 계단위치에서 바로 전 계단과 세 계단 전의 합과 두 계간 전 중 큰값을 기준으로 쌓아가면된다.
• 이게 왜 실버?