[이것이 취업을 위한 코딩테스트다] 08. 다이나믹 프로그래밍

01. 1로 만들기

import sys
input=sys.stdin.readline

x=int(input())
arr=[0]*30001

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

 

02. 개미 전사

import sys
input=sys.stdin.readline

n=int(input())
food=list(map(int,input().split()))

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

print(d[n-1])

 

03. 바닥 공사

import sys
input=sys.stdin.readline

n=int(input())
arr=[0]*1001
arr[1]=1
arr[2]=3

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

 

04. 효율적인 화폐 구성

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
money=[int(input()) for _ in range(n)]
d=[10001]*(m+1)

d[0]=0
# 다이나믹 프로그래밍 진행(보텀업) : money를 가지고 갱신
for i in range(n):
    for j in range(money[i],m+1):
        if d[j-money[i]]!=10001:
            d[j]=min(d[j],d[j-money[i]]+1)

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