LeetCode 322: Coin Change

📊 결과

💻 내 코드 (Try 1)

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0)return 0;

        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0]=0;
        for(int coin: coins){
            if(amount>=coin){
                dp[coin]=1;
            }
        }

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

        if (dp[amount]>amount){
            return -1;
        }else{
            return dp[amount];
        }
    }
}

📝 평가

✔ 잘한 점

  1. Unbounded Knapsack DP 이해
    • 동전을 무한번 사용 가능
    • dp[i] = 금액 i를 만드는 최소 동전 개수
  2. 불가능 처리
    • amount+1로 초기화
    • 최종 확인으로 -1 반환

✦ 개선점

불필요한 코드

// ✘ 중복 처리
for(int coin: coins){
    if(amount>=coin){
        dp[coin]=1;
    }
}

이후 메인 루프에서 자동으로 처리된다.

✨ 최적화된 풀이

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        
        for(int i=1; i<=amount; i++){
            for(int coin: coins){
                if(i >= coin){
                    dp[i] = Math.min(dp[i], dp[i-coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

💡 핵심 인사이트

점화식:

dp[i] = min(dp[i-coin] + 1) for all coins

예시: coins=[1,2,5], amount=11

dp[11] = min(
    dp[10] + 1,  // 동전 1 사용
    dp[9] + 1,   // 동전 2 사용
    dp[6] + 1    // 동전 5 사용
)

📚 관련 개념

🎓 다음 단계

유사 문제

  1. LeetCode 377: Combination Sum IV
  2. LeetCode 518: Coin Change 2
  3. 백준 2294: 동전 2

🏷️ Keywords

#LeetCode #DP #CoinChange #UnboundedKnapsack #Java