Coin Change (DP)

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

이 문제는 자신이 카페 알바생이라고 생각하며 풀어보자.

당신은 손님들에게 거스름돈을 어떻게 남겨줄것인가?

손님들은 되도록이면 잔돈의 수가 적기를 바랄 것이다.

아마 보통 알바생들은 가장 큰 단위의 돈부터 집어들고 점점 더 작은 단위로 내려가면서 돌려줘야 할 거스름돈이 딱 0원일 때까지 돈을 집어들것이다.

예를 들어, 손님이 당신에게 10000원짜리 한 장을 건네며 아메리카노 한잔을 주문했다.

이 매장의 아메리카노 가격은 4100원이다. 당신은 5900원을 손님에게 돌려줘야한다.

분명히 당신은 포스에서 5000원짜리 지폐 한 장을 집어들고 500원짜리 동전을 하나 집어들고 100원짜리 동전 4개를 집어서 손님에게 건넬 것이다.

이 과정을 코드로 나타내보자.

def coinChange(coins, amount) :
 
    def helper(remain) :
 
        if remain < 0 : return -1
        if remain == 0 : return 0
 
        ans = float("inf")
 
        for coin in coins :
 
            tmp = helper(remain-coin) # 남은 돈 계산
 
            if tmp != -1 :
                ans = min(tmp+1, ans)
 
        return ans if ans != float("inf") else -1       
    
    return helper(amount)
    
coinChange([5000, 1000, 500, 100], 5900)

실행 과정을 그림으로 나타내보자.

음.. 조금 더 개선해 볼 수는 없을까?

이미 계산한 노드의 값을 다시 계산하지 않도록 메모이제이션 방식을 적용해보자.

def coinChange(coins, amount) :
 
    def helper(remain, memo) :
 
        if remain < 0 : return -1
        if remain == 0 : return 0
 
        if memo[remain] != float("inf") :
            return memo[remain]
 
        ans = float("inf")
 
        for coin in coins :
            tmp = helper(remain-coin, memo)
            if tmp != -1 :
                ans = min(tmp+1, ans)
 
        memo[remain] = ans if ans != float("inf") else -1   
        return memo[remain] 
    
    memo = [float("inf")]*(amount+1)
    return helper(amount, memo)

조금 더 개선해볼 수는 없을까? 

재귀적으로 문제를 해결한다면 콜 스택에 함수들이 계속 쌓이기 때문에 메모리 낭비가 심할 것이다.

반대로(bottom-up 방식) 생각을 해보자.

어쨌거나 저쨌거나 우리의 목표는 잔돈의 수를 최소한으로하여 5900원을 만드는 것이다.

100원부터 시작해보자.

100원이 될 수 있는 경우의 수는? 1이다. 

왜? 0원이 100원이 되려면 100원짜리 동전을 하나 집어드는 방법밖에 없기때문이다. (매장 내에는 5000원, 1000원, 500원, 100원만 있다고 가정.)

이것을 식으로 어떻게 표현할 수 있을까?

이렇게 표현하면 되지않을까?

그렇다면 500원은?

첫번째 식은 400원일 때 100원짜리 하나를 집어드는 경우이고 두번째 식은 0원일 때 500원짜리 하나를 집어드는 경우이다.

이제 수식을 세워보자.

우리는 잔돈의 수를 최소한으로 해야하기 때문에 가장 작은 수를 찾아 1을 더해주면된다.

이제 이 생각을 코드로 표현해보자.

def coinChange(coins, amount) :
 
    dp = [float("inf")]*(amount+1)
    dp[0] = 0
 
    for i in range(amount+1):
        for coin in coins :
            if coin <= i :
                dp[i] = min(dp[i-coin]+1, dp[i])
 
    return dp[-1] if dp[-1] != float("inf") else -1

매우 간결해졌다. 

이 해결법의 시간복잡도는 , 공간복잡도는 이다.

이제 그만 퇴근합시다..🖐

문제 :

https://leetcode.com/problems/coin-change/