[LeetCode] Coin Change - Java(자바)

문제

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.

문제 해석

여러 종류의 동전을 나타내는 정수 배열 coins가 주어집니다. 또한, amount라는 총 금액이 주어집니다.

이 금액을 만들기 위해 필요한 최소 동전의 수를 반환하세요. 만약 이 금액을 주어진 동전으로 만들 수 없다면 -1을 반환하세요.

각 동전의 개수는 무한히 많다고 가정할 수 있습니다.

제한사항

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

입출력 예

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: -1

풀이

문제 파악

• 동전의 종류(coins)와 목표 금액(amount)이 주어졌을 때, 목표 금액을 만들기 위해 필요한 최소 동전 개수를 구하는 문제
• 주어진 동전 내의 조합으로 목표 금액을 만들 수 없을 경우 -1을 반환

접근 방법

• 문제의 답은 목표 금액을 만들 수 있는 동전의 조합 중 동전의 개수가 최소가 되는 값이며, 이를 위해 특정 금액 별 구성 동전의 개수가 최소인 경우 구하는 점화식을 구해야 한다. 이 경우, 다음과 같은 점화식을 유도할 수 있다.

• 해당 점화식을 바탕으로 Bottom-Up 방식의 코드를 구현하면 다음과 같다.

1. 금액을 가리키는 인덱스에 값으로 동전 개수를 저장하는 배열 생성하고 모든 값을 Integer.MAX_VALUE로 초기화. 0번째 값에는 0을 저장
2. for 문 내에서 목표 금액까지의 각 금액을 만들 수 있는 최소 동전 개수를 각각 저장/갱신함
   • 조합 가능한 금액(인덱스)와 해당 금액을 만들 수 있는 최소 동전 개수(값)으로 이루어진 배열 dp 완성
3. 배열[목표 금액]의 값이 Integer.MAX_VALUE가 아닐 경우(값이 갱신되었을 경우), 해당 값이 목표 금액을 만들기 위해 필요한 최소 동전 개수가 됨
   • 배열[목표 금액]의 값이 Integer.MAX_VALUE일 경우, -1 반환

코드 구현

import java.util.*;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < amount; i++) {
            if (dp[i] == Integer.MAX_VALUE) continue;
            for (int coin : coins) {
                // Prevent overflow by checking if i + coin will overflow
                if (coin > 0 && i <= amount - coin) {
                    dp[i + coin] = Math.min(dp[i + coin], dp[i] + 1);
                }
            }
        }
        return (dp[amount] == Integer.MAX_VALUE) ? -1 : dp[amount];
    }
}