[LeatCode] Medium 322 Coin Change (Java)

문제 링크

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

풀이

1. 접근 방법

1. 동적 계획법(DP) 사용
   • dp[i]를 총액 i를 만들기 위한 최소 동전 개수로 정의
2. 초기화
   • dp[0] = 0으로 설정
   • 나머지 값은 Integer.MAX_VALUE로 초기화하여 불가능한 상태를 나타냄
3. 반복문으로 DP 배열 채우기
   • 1부터 amount까지 모든 금액에 대해 가능한 최소 동전 개수를 계산
   • 현재 금액(i)을 만들기 위해 각 동전을 사용했을 때, 해당 동전을 사용하기 전 금액(i - coin)이 계산 가능한 경우, 최소 동전 개수로 갱신
     ex) 5원을 만들기 위해 4원을 만들기 위한 동전 갯수에 1원짜리 동전 1개를 추가. dp[5] = dp[4] + 1
4. 결과 확인
   • dp[amount] 값이 여전히 Integer.MAX_VALUE라면 총액을 만들 수 없으므로 -1 반환
   • 그렇지 않으면 dp[amount] 값 반환

2. 의사 코드

함수 coinChange(동전 배열 coins, 총액 amount):
    dp 배열을 크기 (amount + 1)로 생성 후 모두 Integer.MAX_VALUE로 초기화
    dp[0] = 0  # 총액이 0일 경우 필요한 동전 개수는 0

    for i = 1 to amount:
        for coin in coins:
            if coin <= i:
                if dp[i - coin] != Integer.MAX_VALUE:
                    dp[i] = min(dp[i], dp[i - coin] + 1)

    if dp[amount] == Integer.MAX_VALUE:
        return -1  # 총액을 만들 수 없는 경우
    return dp[amount]  # 최소 동전 개수 반환

3. 시간 복잡도

• 외부 반복문: amount번 실행
• 내부 반복문: coins.length번 실행
• 전체 시간복잡도: O(amount × coins.length)

구현

import java.util.Arrays;

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 = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin > i) {
                    continue;
                }

                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];
    }
}