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

문제

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

14916번: 거스름돈

---

문제 요약

거스름돈 액수 n을 입력 받고, 2원과 5원 두 종류의 동전만으로 지불할 때, 최소한으로 사용할 수 있는 동전 개수를 출력한다.

+ 거슬러 줄 수 없으면 -1을 출력한다.

---

코드

import sys
input = __import__('sys').stdin.readline

n = int(input())
# 거스름돈 액수

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)
    # 거스름돈 i원의 최소 동전 개수 저장. (100000은 임의의 큰 값)
    dp[2] = 1
    dp[4] = 2
    dp[5] = 1

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

    print(dp[n])

---

코드 설명

1. 거슬러 줄 수 없는 경우는 n이 1 또는 3일 때 밖에 없으므로, n이 4일 때까지는 if문을 이용해 따로 출력해준다.

 

2. dp[i]는 i원을 2원과 5원으로 거슬러 줄 때 최소한으로 사용할 수 있는 동전 개수를 저장하는 메모이제이션 테이블이다.

 

3. dp[i]를 구하는 방법은 i원에서 2원을 뺀 값과 5원을 뺀 값을 거슬러 줄 때 필요한 최소 동전 개수를 비교하여 더 작은 값에서 1을 더한 값이다.

+ 1을 더하는 이유는 이전 값에서 2원 또는 5원을 하나 더 내야하기 때문이다.

 

4. Dynamic Programming의 Bottom Up 방식을 사용한다.

=> 반복문을 통해 dp[i]값을 구하기 위해 dp[0]부터 쭉 구해가며 dp[n] 값을 업데이트한다.