[Leetcode][Java] 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.

 

integer 배열인 coins을 입력값으로 받고, 해당 배열에 들어있는 값들은 각각 다른 코인의 액수이다.

그리고 액수의 총합을 입력값으로 받는다.

 

총합의 금액을 만들 수 있는 최소한 작은 코인 개수를 반환하여라.

만약 총합의 값을 주어진 coins 배열로 만들 수 없다면 -1을 반환해라.

 

coins 배열에 들어있는 값의 코인의 갯수는 무한하다고 생각하면 된다.

---

이 문제는 주어진 문제를 sub 문제로 쪼개서 해결할 수 있다. 

예를 들어 입력 받은 총합이 n이고 [ 2 , 3, 5 ] coin 배열을 입력받았다고 하면 

f( n ) = Min( f(n-5), f(n-3), f(n-2) ) + 1 로 쪼개서 생각할 수 있다. 

    private int dp(int[] coins, int remains, int[] rst) {

        if (remains < 0)
            return -1;
        if (remains == 0)
            return 0;
        if (rst[remains - 1] != 0)
            return rst[remains - 1];

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int temp = dp(coins, remains - coin, rst); // make sub problem 
            if (temp >= 0 && temp < min) {
                min = temp + 1; // add 1 -> add self count
            }
        }
        rst[remains - 1] = min == Integer.MAX_VALUE ? -1 : min;
        return rst[remains - 1];
    }

그럼 다음으로 해당 코드를 호출하는 부분을 살펴 보자.

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }

        int[] rst = new int[coins.length];
        return dp(coins, amount, rst);
    }

 

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

Coin Change - LeetCode