[LeetCode] 322. Coin Change

322. Coin Change

LeetCode

 

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.

서로 다른 권종의 동전들을 나타내는 정수 배열 coins와 총액을 나타내는 정수 amount가 주어집니다.
그 금액을 만드는 데 필요한 가장 적은 동전의 개수를 반환하십시오. 만약 어떤 동전의 조합으로도 그 금액을 만들 수 없다면 -1을 반환하십시오.
각 종류의 동전은 개수가 무한하다고 가정해도 좋습니다.

 

Example

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

---

1. 문제 요구사항 분석

amount 금액을 만드는데 필요한 가장 적은 동전의 개수 구하기

 

2. 접근 전략

😭 1. 코인을 내림차순으로 정렬하기 2. amount를 내림차순으로 한 걸로 나누기 → 가장 큰 금액부터 채우는 방식은 거스름돈의 단위가 서로 배수 관계일 때(예: 500원, 100원, 50원, 10원)는 성립하지만, 위 예시처럼 배수 관계가 아닐 때는 성립하지 않는다.

 

😄 Dynamic Programming으로, 0원을 만드는데 필요한 동전의 개수부터 amount 까지 배열에 저장하기

dp[i] = min(dp[i], dp[i - c] + 1)

 

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];

        // 모든 칸을 max값으로 채움
        Arrays.fill(dp, max);
        
        dp[0] = 0;

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

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

coins = [1,2,5], amount = 11

i = 1

→ i = 1, coin = 1 : dp[1] = Math.min(12, dp[0] + 1); = 1

 

i = 2

→ i = 2, coin = 1 : dp[2] = Math.min(12, dp[1] + 1) = 2

→ i = 2, coin = 2 : dp[2] = Math.min(2, dp[0] + 1) = 1

 

i = 3

→ i = 3, coin = 1 : dp[3] = Math.min(12, dp[3 - 1] + 1)  = 2

→ i = 3, coin = 2 : dp[3] = Math.min(2, dp[3 - 2] + 1) = 2

 

...