322. Coin Change

문제

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

 

Return 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.

 

You may assume that you have an infinite number of each kind of coin.

 

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

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Solution

class Solution {
    public int coinChange(int[] coins, int amount) {
        // DP 배열 생성 및 초기화
        // amount + 1로 초기화하는 이유: 어떤 경우에도 amount보다 많은 동전이 필요하지 않음
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0; 

        for(int curAmount=1;curAmount<=amount;curAmount++) {
            for(int coin : coins) {
                if(curAmount>=coin) {
                    dp[curAmount] = Math.min(dp[curAmount], 1 + dp[curAmount-coin]);
                }
            }
        }

        // 불가능한 경우 -1 반환, 가능한 경우 최소 동전 개수 반환
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

풀이

이 문제를 동적 프로그래밍으로 풀이한 이유와 과정을 상세히 설명해드리겠습니다.

 

왜 동적 프로그래밍을 사용했나요?

• 이 문제는 '최소' 동전 개수를 찾는 문제입니다.
• 작은 금액의 최적해를 이용해 큰 금액의 최적해를 구할 수 있습니다.
• 동일한 하위 문제가 반복해서 발생합니다. 예를 들어, coins=[1,2,5], amount=11 인 경우:
• 11원을 만들기 위해 5원을 사용하면, 남은 6원을 만드는 문제가 됩니다.
• 6원을 만드는 문제는 다른 경우에서도 반복해서 등장할 수 있습니다.

초기값을 amount + 1로 설정한 이유:

Arrays.fill(dp, amount + 1);

• 어떤 금액을 만들기 위해 필요한 동전의 개수는 항상 금액 자체보다 작거나 같습니다.
• 따라서 amount + 1은 '불가능'을 나타내는 값으로 적절합니다.
• 마지막에 이 값이 그대로 있다면 해당 금액을 만들 수 없다는 의미가 됩니다.

회고

dp 배열을 초기화할 때 모든 값을 amount + 1로 채우는 부분에서 이해하는데 시간이 걸렸다. 중첩 반복문 사용은 보통 시간 복잡도 문제로 고려하지 않지만, 입력 조건을 확인한 후 충분히 사용해도 성능 문제가 없다는 판단을 내렸다.

• 1 <= coins.length <= 12
• 0 <= amount <= 104