Coin Change

🔗 문제 링크

https://leetcode.com/problems/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.

⚠️ 제한사항

• $1 <= coins.length <= 12$

• $1 <= coins[i] <= 2^{31} - 1$

• $0 <= amount <= 10^4$

---

🗝 풀이 (언어 : Java)

옛날에 풀었던 거스름돈 그리디 문제인 줄 알고 쉽게 생각했는데, 그건 안되는 케이스가 없고 딱 나누어 떨어지는 케이스고 이것은 안되는 케이스도 포함한 문제이다. 이 문제는 DP 문제이다. 풀이를 보고 다시 작성해보았다. 해당 숫자를 만들기 위해 해당 숫자 전의 숫자들을 만들기 위한 코인 수를 이용해서 계속 최소값을 비교해 갱신한다. dp배열의 초기값을 불가능한 값으로 해주어서 답이 존재하지 않는 경우도 인지할 수 있게 해야한다.

class Solution {
    public int coinChange(int[] coins, int amount) {
        // DP 배열, 0부터 시작해서 N까지 칸을 만들기위해 N+1
        int[] dp = new int[amount + 1];
        int len = dp.length;
        // 배열을 0번째 칸 빼고 나머지를 불가능한 값인 amount+1로 초기화
        // 정답 숫자의 칸에 amount+1이 그대로면 정답 존재안하는 것
        for (int i = 1; i < len; i++)
            dp[i] = amount + 1;
        // DP
        for (int i = 1; i < len; i++) {
            for (int coin : coins) {
                // 앞에서 해당 타겟 숫자를 만드는데 필요한 코인이 존재할 경우만
                if (i - coin >= 0)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}