2023.05.24 풀이
import sys
input=sys.stdin.readline
t=int(input())
arr=[0]*(301)
d=[0]*(301)
for i in range(t):
arr[i]=int(input())
d[0]=arr[0]
d[1]=arr[0]+arr[1]
d[2]=max(arr[0]+arr[2], arr[1]+arr[2])
for i in range(3, t):
d[i]=max(d[i-3]+arr[i-1]+arr[i], d[i-2]+arr[i])
print(d[t-1])
다른 풀이
n=int(input())
s=[int(input()) for _ in range(n)]
dp=[0]*(n)
if len(s)<=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])
print(dp[-1])
check point
- 점화식 풀이 참고 1, 2
- 점화식을 잘 모르겠으면 끝에서 부터 내려오기/d[0]부터 바텀업으로 생각해보기
- 런타임에러 : d와 arr의 범위를 t에 관련해서 선언하지 않으면 런타임에러가 났음