[LeetCode] Coin Change

1. 문제 : https://leetcode.com/problems/coin-change/

동전을 최소로 사용해 특정 숫자를 만들기 (중복사용 가능)

 

2. 풀이

dp 문제

동전 최소크기인 11보다 +1수를 max값으로 dp에 저장하고,

해당 숫자를 만들 수 있는 최소사용횟수를 비교하며 구하는 방식 (어려움...)

 

ex)

숫자 2는 코인2 한번에 만들 수 있음 -> 이걸 어떻게 dp로 자동으로 하냐? -> dp[i-money즉 0]  +1 과 dp[i] 값 중 비교해서 넣으면됨

 

3. 코드

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;

        if(amount==0)
            return 0;

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