달나라 토끼를 위한 구매대금 지불 도우미(백준 17212)

 다이나믹 프로그래밍을 사용하는데 동전의 값으로 나누어 떨어지는 지 안 떨어지는 지 경우를 나누고 

배열을 완성하면 된다. 

import sys 
input = sys.stdin.readline 

n= int(input())
arr= [i for i in range(n+1)]

coins  =[1,2,5,7]
# print(arr)

for coin in coins :
    if coin == 1 :
        continue 
    for k in range(1,n+1):
        if coin <= k :
            if( k% coin ==0) :
                arr[k] = min((k//coin),arr[k-coin]+1 )
            else :
                arr[k] = min(arr[k] ,arr[k-coin]+1 )
                
print(arr[-1])