[파이썬 PYTHON · 자바 JAVA] LeetCode【Coin Change】

 

Coin Change - LeetCode

---

자바 코드

import java.util.*;
class Solution {
    public int coinChange(int[] coins, int amount) {
        long[] dp = new long[amount+1];
        dp[0]=0;

        for(int i=1;i<=amount;i++){
            dp[i] = Integer.MAX_VALUE;
            for(int coin : coins){
                if(i-coin<0){
                    continue;
                }
                dp[i]= Math.min(dp[i],dp[i-coin]+1);
            }
        }
        System.out.println(Arrays.toString(dp));
        if(dp[amount]!=Integer.MAX_VALUE){
            return (int)(dp[amount]);
        }else{
            return -1;
        }
    }
}

파이썬 코드

class Solution(object):
    def coinChange(self, coins, amount):

        dp =[0]

        for i in range(1,amount+1):
            dp.append(1e9)
            for coin in coins:
                if i-coin<0:
                    continue
                dp[i]=min(dp[i-coin]+1,dp[i])

        ans = dp[amount] if dp[amount] !=1e9 else -1
        
        return ans

 

갖고 있는 동전으로 i-coin 계산을 다 해본다.

 

dp[i-coin] 값이 1e9가 아니라면 갖고 있는 동전으로 값을 구할 수 있다는 뜻이므로 dp[i-coin]+1 한값을 dp[i]에 업데이트 한다. (최솟값으로)

 

만약, i-coin<0 이면 위 과정을 무시한다.

---

 

---

---

---

위 과정을 계속 반복하고, dp[amount]가 1e9가 아닌 경우에만 답 출력