[LeetCode] 322. Coin Change

문제

DP 문제이다.

여러 동전의 가격 coins가 주어질 때, (각 동전의 가격은 다름)

amount 가격을 만들기 위해 사용하는 동전의 최소 개수를 구하라.

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

Coin Change - LeetCode

 

풀이

예시)

amount : 만들어야 하는 가격

사용할 수 있는 동전들 : 1원, 2원, 5원

a원 동전을 하나 사용한다고 할 때, amount를 만들기 위한 최소 동전의 개수를 구하기 위해서는

(amount - a) 원을 만드는 최소 동전의 개수에 1을 더하면 된다. (a원 동전을 1개 사용했으므로)

 

따라서 i원을 만들 때, 사용할 수 있는 동전들을 하나씩 사용해보면서 그중 가장 최소 동전을 사용하는 개수를 저장하면 된다.

 

코드

public int coinChange(int[] coins, int amount) {

        int[] minNums = new int[amount + 1];
        Arrays.fill(minNums, amount + 1);
        minNums[0] = 0;
        Arrays.sort(coins);

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    minNums[i] = Math.min(minNums[i], minNums[i - coin]);
                } else {
                    break;
                }
            }
            minNums[i]++;
        }

        return minNums[amount] > amount ? -1 : minNums[amount];
    }