[리트코드]322. Coin Change

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [1e9] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
                
        return dp[amount] if dp[amount] != 1e9 else -1

사용언어 Python3

난이도    Medium

 

문제풀이과정

해당 문제를 보자마자 Dynamic..아.. DP를 떠올렸다.. 가장 대중적인 DP문제라고 생각한다.

만들어야하는 값을 DP 배열로 만든다. 0은 포함하지 않기에 +1

내가 가진 코인으로 해당 값을 만드는데 최소한의 코인이 몇개 필요한지 구한다.

먼저 1코인으로 값11을 만든다 생각하면 dp 배열은 1,2,3,4....11로 구성될것이다.

다음에 가진 코인이 2코인이라면 값 11을 만들때 dp배열은 1,1,2,2,...6 일 것이고

이것을 가진 코인 모두와 반복시킨다. 그리고 해당 배열의 11번째 값을 반환하고

11번째 값이 초기 값에서 변경된 점이 없다면 -1을 리턴한다.