[LeetCode] 322 Coin Change

Description

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

Example 4:

Input: coins = [1], amount = 1
Output: 1

Example 5:

Input: coins = [1], amount = 2
Output: 2

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

---

풀이

• 동전의 단위가 배열로 주어지고, 총 금액이 주어질 때 총 금액을 달성할 수 있는 최소 동전의 개수를 반환하는 문제이다.

• 이전 단계의 동전 개수에서 1개만 더해주면 현재 동전 개수가 나온다. (sub problem으로 나뉘어진다.)

• 1번 예시의 경우

  F(11) = min( F(11-1=10), F(11-2=9), F(11-5=6) ) + 1

• top down 보다 빠른 bottom up의 DP로 풀었다.
  0 부터 하나씩 답을 찾아간다.

  • F(0)=0, F(1)=1, F(2)=1, F(3)=-1, F(4)=-1, F(5)=1, F(6)=2, ..., F(11)=3
  • F(6)=min( F(6-1=5), F(6-2=4), F(6-5=1) ) + 1

• 값을 저장할 배열을 만든다.

• 배열에서 0일 때 값은 0으로 미리 넣어준다. (base case)

• 배열을 처음부터 끝까지 돈다.

  • coins 배열도 하나씩 돈다.
  • 비교할 인덱스 값을 compareIndex에 넣는다.
  • 만약 인덱스가 범위 안에 있고, 해당 인덱스의 값이 -1이 아니며 minCount보다 값이 작다면 minCount를 비교인덱스의 값으로 바꿔준다.
  • 만약 minCount가 -1이라면 동전으로 갈 수 없다는 뜻이므로 -1을 값 배열에 -1을 넣어주고, 아니면 minCount에 1을 더한 값을 넣어준다.

• 마지막으로 값 배열의 마지막 값을 반환한다.

---

코드

class Solution {
    public int coinChange(int[] coins, int amount) {
        int minCount, compareIndex;
        int[] arr = new int[amount + 1];
        arr[0] = 0;

        for (int i = 1; i < arr.length; i++) {
            minCount = -1;
            for (int j = 0; j < coins.length; j++) {  // 2, 3, 5
                compareIndex = i - coins[j];
                if (compareIndex >= 0 && arr[compareIndex] != -1 && (minCount == -1 || minCount > arr[compareIndex])) {
                    minCount = arr[compareIndex];
                }
            }
            arr[i] = (minCount == -1) ? -1 : minCount + 1;
        }

        return arr[amount];
    }
}