5.7 거스름돈 최적화 - DP

이번에는 DP를 이용해서 동전 문제를 풀어본다.
이상하게 다른 절들에 비해 알고리즘에 대한 상세한 소개가 별로 안되어있다.
초반에 탐욕 알고리즘을 설명해놔서 그런가;;

재귀 호출을 사용할 때와 비슷한 방법으로 DP로 풀 수 있으나
다만 적은 액수부터 큰 액수를 구하는 방향으로 진행하는 게 차이가 있다.
작성한 소스는 다음과 같다.

def minCoins_dp(coin, n, s):
    ar = [MAX_INT for _ in range(s+1)]
    ar[0] = 0

    for i in range(1, s+1):
        for j in range(n):
            if coin[j] <= i:
                temp = ar[i - coin[j]]
                if temp != MAX_INT and temp + 1 < ar[i]:
                    ar[i] = temp + 1

    return ar[s]

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

여기서 핵심은
i가 정해진 금액인 s에 도달할 때까지 순회하면서
j가 0부터 코인의 종류를 순회하면서 채워나가되
ar에서 금액의 값(i)에서 동전을 뺀(coin [j]) 값에 +1 한 값이 ar [i] 보다 작으면 업데이트를 해주는 부분이다.

i가 1원부터 s까지 도달하는 로직을 생각해내는 게 쉽지 않을 듯..

나중에(한달 정도 후) 다시 풀어보라고 하면 풀수 있을까? 싶은 ㅋㅋㅋㅋㅋㅋ