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

n = int(input())
dp = [-1] * (n+5)

dp[2] = 1
dp[3] = -1 
dp[4] = 2
dp[5] = 1

for i in range(6, n+1):
    if dp[i-5] != -1:
        dp[i] = min(dp[i-2]+1, dp[i-5]+1)
    else:
        dp[i] = dp[i-2]+1
        

print(dp[n])

문제

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

예시

코드

 

 

 

풀이

예를 들어 거스름돈이 8원일 때 동전을 최소로 내는 방법( = dp[8])은

1. 거스름돈이 6원일때 최소개수로 내는 방법( = dp[6]) + 2원 내기 => dp[6] + 1

2. 거스름돈이 2원일 때 최소개수 내는 방법( = dp[2]) + 6원 내기 => dp[2] + 1

둘 중 더 작은 값이다

그러므로 점화식은 min(dp[i-2],dp[i-5]) + 1 로 나타낼 수 있다