[리트코드] 322. Coin Change

문제

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

#Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

#Example 2:
Input: coins = [2], amount = 3
Output: -1

#Example 3:
Input: coins = [1], amount = 0
Output: 0

풀이

그리디로 접근하다가 런타임 에러가 나서 머리를 꽁꽁싸메다 dp(dynamic programming) 접근법을 새롭게 알았다.
큰 문제를 작은 문제로 생각해 보자.
coins = [2, 5] , amount = 10
amount 가 0 일때 필요한 동전의 최소 개수는?

0이다. 그럼 amount가 1일때 필요한 동전의 최소 개수는 어떻게 구할까. 동전 2, 5원으로 만들수 있는 것은 없다.
그럼 amount 가 2일때 필요한 동전의 최소 개수는 ? 동전 2원을 하나 사용해 보자. 그럼 amount 2 - 2 = 0 이다. amount = 0 일때 필요한 동전의 [최솟값] 에다 2원을 하나 사용한 꼴이 된 것이므로
[최솟값] +1 즉 0 + 1 = 1 이다. amount 가 3일때 필요한 동전의 최소 개수는 ? amount(3) - 2 = 1
amount 가 1일때 만들수 없는 것을 알수 있으니깐 넘어간다. 이런 로직으로 amount 11까지 가면 11원을 만들기 위해 필요한 동전의 개수를 알수 있다.

코드

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0 )return 0;
        
        int dp[] = new int[amount+1];
        /* 최댓값으로 채운다. */
        Arrays.fill(dp,10001);
        dp[0] = 0;
                    
        for(int i = 0 ;i < coins.length ;i++){
            for(int j = 1 ;j < amount+1; j++){
                if(j - coins[i] >= 0 ){
                    dp[j] = Math.min(dp[j], dp[j - coins[i]]+1);
                }
            }
        }
        return dp[amount] == 10001? -1 : dp[amount];
    }
}