5.7 거스름돈 최적화 - 재귀

오늘은 탐욕 알고리즘으로 잘 알려진 동전 문제 중에 하나를 풀어본다.
액면가가 다른 여러 종류의 동전을 제한 없이 사용 가능할 때
어떤 금액을 지불하는 데 사용 가능한 동전 개수의 최솟값을 구하는 문제다.

탐욕 알고리즘을 사용한다면, 가장 큰 액면가의 동전을 먼 자 사용해서 금액을 채워나가면 된다.
그러나 특정 조건(10원, 50원, 100원, 500원 등 가능한 조합)이 아니라면 탐욕 알고리즘을 사용했을 때,
최적의 값을 찾아낼 수 없다.

그렇기에 재귀 호출을 사용해서 풀어본다.
minCoins(S) = 1 + MIN(minCoins(S - coin [0]), minCoins(S - coin [1]),... minCoins(S - coin [N-1]))
위의 식이 점화식이라는데.. 좀 이해가 안 된다 ㅠㅠ 이걸 어찌 구현하라는 거지.
그리고 종료 조건은 S가 0인 경우다. 
책에 나온 소스를 파이썬으로 바꿔서 코딩하면 다음과 같다.

import sys
sys.setrecursionlimit(10**5)
def minCoins(coin, n, s):
    if s == 0:
        return 0
    result = 987654321
    for i in range(n):
        if coin[i] <= s:
            temp = minCoins(coin, n, s - coin[i])

            if temp + 1 < result:
                result = temp + 1
    return result

coin = list(map(int, input().split()))
s = int(input())
n = len(coin)
print(minCoins(coin, n, s))

위에 소스를 실행하면 효율이 매우 똥망이다..
2 5 10 15
60
정도로 사람이 구해도 그냥 4가 나오는 계산을 엄청 오래 한다 ㅋㅋㅋㅋㅋㅋㅋㅋ
반복 계산이 매우 많은 듯 ㅠㅠ

내일은 이걸 DP로 바꿔보는 작업을 할 예정!