[DP/동적계획법] 백준 14916 거스름돈 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14916번: 거스름돈

 

 

2. 문제 풀이

거스름돈을 2원과 5원 동전으로 거슬러주는 문제입니다. 이때 거슬러주는 동전의 개수는 최소가 되어야 합니다.

 

2022.01.31 - [Algorithm] - [그리디/Greedy] 백준 11047 동전 0 - Python

[그리디/Greedy] 백준 11047 동전 0 - Python

 각 동전의 단위가 배수가 아니므로 그리디 알고리즘은 사용할 수 없습니다. 우리나라의 화폐단위는 10, 50, 100, 500, 1000, 5000, 10000, 50000으로 하위 화폐로 상위 화폐의 액수를 만들 수 있습니다.

 그래서 무조건 고액권부터 고려해서 거스름돈을 계산하면 쉽게 해결됩니다. 하지만 2원과 5원은 배수 관계가 아니므로 동적계획법으로 일일이 경우의 수를 고려해야 합니다.

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

# 입력
n = int(input())

# DP
if n == 1:
    print(-1)
elif n == 2:
    print(1)
elif n == 3:
    print(-1)
elif n == 4:
    print(2)
else:
    dp = [100000] * (n + 1)
    dp[2] = 1
    dp[4] = 2
    dp[5] = 1

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

    print(-1 if dp[n] == 100000 else dp[i])

 1부터 5까지는 세팅을 해줍니다. 그래야 dp[i-5]에서 오류가 나지 않습니다.

 

dp[i] = min(dp[i], dp[i-2]+1, dp[i-5]+1)

 가장 중요한 코드입니다.

 dp[i-2]는 2원을 거슬렀을 경우를 뜻하며, dp[i-5]는 5원을 거슬렀을 경우를 뜻합니다. 여기서 dp는 거스름돈 동전의 개수입니다.

 

dp[10] = min(dp[10], dp[8]+1, dp[5]+1)

 예를 들어 i = 10인 경우, 8원에서 2원을 더한 경우(dp[8]+1)와 5원에서 5원을 더한 경우(dp[5]+1) 중 최소값을 찾습니다.

 이렇게 5부터 n까지 세 가지 경우 중에 최소값을 갱신하며 정답을 구합니다.