leetcode 322 - Coin Change

dp문제.. 매우 어렵다.

 

greedy로 접근하기 쉬운데, 코인과 amount가 greedy로 풀리지 않는 경우가 있다.

 

DFS적 접근으로 결정 트리를 그려보면 이해하기 쉽다.

브루트포스로 amount에서 coins의 경우를 선택해 나간다고 생각해보자.

 

케이스 1 에서 처음 1,2,5 중 하나의 선택을 하게 된다.

 

1을 택했다면 , amount는 10이되고 여기서 또 125의 선택을 반복해 나간다.

예를 5를 택했다면 amount 는 5의 상태로 코인 1,2,5에서의 선택.

 

즉 amount에 따른 subtask가 계속 생긴다고 볼 수 있다. dp bottom up 접근이 가능

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1] * (amount+1)
        dp[0] = 0

        for a in range(1,amount+1):
            for c in coins:
                if a - c >= 0:
                    dp[a] = min(dp[a],1+dp[a-c])

        return dp[amount] if dp[amount] != amount + 1 else -1

amount가 0 인케이스. dp[0] 은 0이다.

dp리스트에 amount에 따른 요소 amount +1개가 있어야 한다(dp[0]포함 개수)

amount+1로 초기화 해주는 이유는 어쨋든간 min연산을 위해 디폴트값으로 큰 값이 필요한데,

코인이 전부 1이라고 해도어쨋건 amount+1을 넘을

수 없기 때문이다.

 

반복문으로 a (amount)즉 서브케이스가 되는 모든 것들을 스텝바이 스텝 구해나간다.

반복문으로 amount에서 차차 하나씩 코인을 대입해나간다.

코인이 amount를 오버하지 않고 대입되는 경우라면. if a -c >= 0:

dp[a]에 코인 개수 1개를 추가하고 서브태스크 [a-c]의 개수를 더한다.

 

바텀업 방식이기에, 포문의 범위와 연산을 최대한 줄인채로 dp[1]부터 재귀를 거듭해 dp[amount]까지 구할 수 있다.

 

dp[amount]가 디폴트값에서 바뀌었다면 맞는 결과값이 하나라도 있었다느 ㄴ판단하에 dp[amount]반환

아니라면 -1반환