다이나믹 프로그래밍 예제

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

N = int(input())

a = [0]*(N+1) # 길이 N+1, a[N] 참조 가능

a[1] = 0

for i in range(2, N+1):
    a[i] = 1+a[i-1]
    
    if i%3 == 0:
        a[i] = min(a[i], 1+a[i//3])
    if i%2 == 0:
        a[i] = min(a[i], 1+a[i//2])
        
print(a[N])

 

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

N = int(input())

S = [0]*N

for i in range(N):
    S[i] = int(input())



A = [0]*N
B = [0]*N

A[0] = S[0]
B[0] = S[0]

for i in range(1, N):
    if i >= 2:
        A[i] = S[i]+max(A[i-2],B[i-2])
    else:
        A[i] = S[i]
        
    if i >= 3:
        B[i] = S[i]+S[i-1]+max(A[i-3],B[i-3])
    else:
        B[i] = S[i]+S[i-1]
        
print(max(A[N-1],B[N-1]))