다이나믹 프로그래밍 개념과 예제

다이나믹 프로그래밍

동적할당의 다이나믹과는 다른 개념

1. 큰 문제를 작은 문제로 나눌 수 있다
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

메모이제이션 기법→ 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 캐싱이라고도 함

재귀함수를 사용하여 소스코드를 작성하는 방법→ 탑다운방식 반복문을 이용하여 소스코드를 작성하는 방법→ 보텀업방식

 

1로만들기

x=int(input())
d=[0]*(x+1)

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

print(d[x])

개미전사

n=int(input())
array= list(map(int,input().split()))
d=[0]*100

d[0]=array[0]
d[1]=max(array[0],array[1])
for i in range(2,n):
	d[i]=max(d[i-1],d[i-2]+array[i])
print(d[n-1])

바닥공사

n=int(input())
d=[0]*(n+1)

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

BOJ 타일채우기

n=int(input())
d=[0]*31
#d=[0]*(n+1) 햇다가 n=1인 경우에서 인덱스 오류남
d[2]=3
for i in range(4,n+1):
    if i%2==0:
        d[i]=d[i-2]*3+sum(d[:i-2])*2+2

print(d[n])

효율적인 화폐 구성

n,m=map(int,input().split())
array=[]
for i in range(n):
    array.append(int(input()))

d=[10001]*(m+1)
d[0]=0
for i in range(n):
    for j in range(array[i],m+1):
        if d[j-array[i]] != 10001:
            d[j]=min(d[j],d[j-array[i]]+1)

if d[m] == 10001:
    print(-1)
else:
    print(d[m])

BOJ설탕배달

n=int(input())
ans=0
while True:
    if n%5==0:
        ans+=n//5
        print(ans)
        break
    n-=3
    ans+=1
    if n<0:
        print(-1)
        break

효율적인 화폐구성이랑 비슷한 풀이일줄 알았는데 더 쉽게 풀린다