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

문제 링크 : https://www.acmicpc.net/problem/17212

17212번: 달나라 토끼를 위한 구매대금 지불 도우미

알고리즘 수업때 흔히 배우는 거스름돈 문제입니다. 건네주는 돈의 동전의 개수가 최소가 되도록 하는 경우의 동전 개수를 구하면 됩니다. 일상 생활에서 겪는 거스름돈 문제의 경우 그리디 알고리즘으로 최소 개수의 동전/지폐를 구할 수 있지만(정확히는 그렇게 할 수 있도록 단위가 설계되어 있지만) 이 문제의 경우는 그리디로 해결하지 못하는 경우입니다.

n = int(input())
dp = [100001]*(n+1) #지불해야 하는 금액의 MAX
dp[0] = 0 #0원은 동전 0개로 가능
coin = [7, 5, 2, 1] #동전 종류

for m in range(1, n+1): #1원부터 지불해야 하는 n원까지
    for c in coin:
        #동전 액면가보다 지불해야 하는 금액이 클 경우 and
        #동전 c를 주는 것이(dp[m-c]+1) 기존 경우(dp[m])보다 개수를 줄일 수 있는 경우
        if c <= m and dp[m-c]+1 < dp[m]:
            dp[m] = dp[m-c]+1
print(dp[-1])