chapter 8. 다이나믹 프로그래밍

큰 문제를 작은 문제로 나눠,

현재 계산된 수들을 바탕으로 앞으로의 값을 계산하는 프로그래밍이다

중복되는 연산을 피하기 위해 DP테이블에 계산해 놓은 값을 저장해놓는 (메모이제이션 = 캐싱) 기법 을 이용한다

시간복잡도는 O(logn)이다

 

탑다운 방식

재귀 함수 이용

d=[0]*100
 
def fibo(x):
    if x<=1:
        return 1
 
    #이미 계산한 문제라면 그대로 반환
    if d[x]!=0:
        return d[x]
 
    #아직 계산하지 않은 문제
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]
 
print(fibo(99))

 

 

 

바텀업 방식

반복문 이용

d=[0]*100
 
d[1]=1
d[2]=1
n=99
 
for i in range(3, n+1):
    d[i]=d[i-1]+d[i-2]
 
print(d[n])

 

 

 

 

 

1로 만들기

import sys
input=sys.stdin.readline
 
n=int(input())
d=[0]*(n+1)
 
for i in range(2, n+1):
    d[i]=d[i-1]+1
 
    if i%5==0 and d[i]>d[i//5]+1:
        d[i] = d[i//5]+1
    elif i%3==0 and d[i]>d[i//3]+1:
        d[i] = d[i//3] + 1
    elif i%2==0 and d[i]>d[i//2]+1:
        d[i] = d[i//2] + 1
 
print(d[n])

 

 

 

개미전사

import sys
input=sys.stdin.readline
 
n=int(input().rstrip())
arr=list(map(int, input().split()))
d=[0]*n
d[0]=arr[0]
d[1]=max(arr[0], arr[1])
 
#전 창고 vs 전전창고+현재값
for i in range(2, n):
    d[i]=max(d[i-1], d[i-2]+arr[i])
 
print(d[n-1])
 
 
 

 

 

 

바닥공사

import sys
input=sys.stdin.readline
 
n=int(input())
d=[0,1,3]+[0]*(n-2)
 
for i in range(3, n+1):
    d[i]=(d[i-2]*2+d[i-1])%796796
 
print(d[n])
 

 

 

 

효율적인 화폐 구성

import sys
input=sys.stdin.readline
 
n, m = map(int, input().split())
val = [int(input()) for _ in range(n)]
d = [10001]*10001
d[0] = 0
for v in val:
    for j in range(v, m+1):
        d[j] = min(d[j], d[j-v]+1)
if d[m]==10001:
    print(-1)
else:
    print(d[m])