동전 거스름돈 문제

동전 거스름돈 문제

대부분의 경우 그리디 알고리즘으로 해결되나, 그렇지 않은 경우도 존재

ex) 거스름돈이 20원일 때 동전이 16원, 10원, 5원, 1원인 경우(그리디는 16원 1개, 1원 4개의 결과가 나옴)

DP 알고리즘은 모든 동전 거스름돈 문제에 대해 항상 최적해를 도출

 

---

앞서 했던 배낭 문제의 DP 알고리즘에서 배낭의 용량을 1kg씩 증가시켜가며 문제를 해결한 것처럼 거스름돈을 1원씩 증가시켜가며 문제를 해결

 

C[n] = n원을 거슬러 받을 때 사용되는 최소의 동전 수

◼ 500원 동전이 필요하면 (n-500)원의 해(C[n-500])에 500원 동전 1개 추가

◼ 100원 동전이 필요하면 (n-100)원의 해(C[n-100])에 100원 동전 1개 추가

◼ 50원 동전이 필요하면 (n-50)원의 해(C[n-50])에 50원 동전 1개 추가

◼ 10원 동전이 필요하면 (n-10)원의 해(C[n-10])에 10원 동전 1개 추가

◼ 1원 동전이 필요하면 (n-1)원의 해(C[n-1])에 1원 동전 1개 추가

거스름돈을 1원부터 1씩 증가시키면서 거스름돈의 액수를 넘어서지 않는 최대 액면가의 동전부터 위와 같은 계산 수행

C[n] = C[n-d_i] + 1

---

예제

거스름돈 20원

동전 : d₁=16, d₂=10, d₃=5, d₄=1 (d₁>d₂>d₃>...>d_k=1)

거스름돈을 1원씩 증가시키면서 거스름돈의 액수를 넘어서지 않는 최대 액면가의 동전부터 

 

 

import sys
from copy import deepcopy

def make_change_v1(change, coins):
    c = [sys.maxsize for _ in range(change + 1)]
    c[0] = 0
    p = [[] for _ in range(change + 1)]
    
    for won in range(1, change + 1):   # won(거스름돈) 1원부터 change까지
        for d in coins:
            if d <= won and c[won-d] + 1 < c[won]:
                c[won] = c[won - d] + 1
                p[won] = deepcopy(p[won - d])
                p[won].append(d)
    
    return c, p


def test_v1():
    coins = [16, 10, 5, 1]
    N = 31      # 거스름 돈
    
    counts, used = make_change_v1(N, coins)
    print(f"거스름돈: {N}원, 동전 개수: {counts[N]}개")
    print(f"사용된 동전: {used[N]}")
    


# 실행
if __name__ == "__main__":
    test_v1()

 

실행 결과