[백준/Python] 14916번: 거스름돈

문제

https://www.acmicpc.net/problem/14916

 

설명

- DP (다이나믹 프로그래밍)

- 1부터 9까지의 숫자 중에서 -1이 나오는 경우는 1과 3밖에 없다. 그리고 나머지 값들에 대해서는 미리 해당하는 동전 개수를 할당해주었고, 10부터의 숫자는 동일한 규칙을 발견할 수 있다.

    10원 : 5원 * 2 + 2원 * 0 => (5원) + 1개

    11원 : 5원 * 1 + 2원 * 3 => (6원) + 1개

    12원 : 5원 * 2 + 2원 * 1 => (7원) + 1개

     .

     .

 

코드

n = int(input())

    #  0   1  2   3  4  5  6  7  8  9
dp = [-1, -1, 1, -1, 2, 1, 3, 2, 4, 3]

for i in range(10, n+1):
    dp.append(dp[i-5]+1)

print(dp[n])