LeetCode 518: Coin Change II

📊 결과

💻 내 코드 (Try 1)

class Solution {
    public int change(int amount, int[] coins) {
        if (amount==0) return 1;
        int[] dp = new int[amount+1];
        
        for(int i=1; i<=amount; i++){
            for(int coin: coins){
                if(i%coin==0){
                    dp[i]+=1;
                }
                if(coin<i){
                    dp[i]=Math.max(dp[i],dp[i-coin]);
                }
            }    
        }
        return dp[amount];
    }
}

📝 평가

✔ 잘한 점

  1. DP 배열 생성
    • dp[i] = 금액 i를 만드는 방법의 수
  2. 문제 분석 시도
    • 주석으로 케이스별 분석

✘ 문제점

1. 나머지 연산 오류

// ✘ 나누어떨어지는 경우만 카운트
if(i%coin==0){
    dp[i]+=1;
}

i=5, coin=2일 때 2+2+1은 무시된다.

2. Max 연산 사용

// ✘ 경우의 수는 더해야 함
dp[i]=Math.max(dp[i],dp[i-coin]);

조합 문제: 합산 필요 최솟값 문제: Max/Min 사용

3. 중복 카운트

동전 순서를 바꾼 조합을 중복으로 센다.

✨ 최적화된 풀이

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;  // 0원을 만드는 방법 = 1가지
        
        for(int coin: coins){
            for(int i=coin; i<=amount; i++){
                dp[i] += dp[i-coin];
            }
        }
        
        return dp[amount];
    }
}

핵심 차이:

💡 핵심 인사이트

중복 방지 원리

잘못된 순서 (중복 발생):

for(int i=1; i<=amount; i++){
    for(int coin: coins){
        // [1,2]와 [2,1]을 다르게 카운트
    }
}

올바른 순서:

for(int coin: coins){
    for(int i=coin; i<=amount; i++){
        // 동전을 순서대로 고려 → 중복 제거
    }
}

예시: coins=[1,2], amount=3

동전 1만 사용:

dp[1] = 1  // [1]
dp[2] = 1  // [1,1]
dp[3] = 1  // [1,1,1]

동전 2 추가:

dp[2] += dp[0] = 2  // [1,1], [2]
dp[3] += dp[1] = 2  // [1,1,1], [1,2]

📚 관련 개념

🎓 다음 단계

유사 문제

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

연습 포인트

🏷️ Keywords

#LeetCode #DP #CoinChange #조합 #Java #중복제거