Leetcode - 322. Coin Change

문제

동전 종류가 주어질때, 동전을 조합하여 amount 값을 만들 수 있는 동전의 최소 갯수는? (동전 갯수는 무제한 제공된다고 가정)

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

해결 DP top down

int visit[10001];
int coin_amount(int* coins, int coinsSize, int amount){
    int min_amt = INT_MAX;
    int val = 0;
    
    /* base case */
    if (amount == 0)
        return 0;
    if (amount < 0)
        return -1;
    if (visit[amount])
        return visit[amount];
    
    /* recursion */
    for (int i = 0; i < coinsSize; i++) {
        val = coin_amount(coins, coinsSize, amount - coins[i]);
        if (val != -1 && val < min_amt)
            min_amt = val;
    }
    if (min_amt == INT_MAX)
        visit[amount] = -1;   
    else
        visit[amount] = min_amt + 1;
    return visit[amount];
}

int coinChange(int* coins, int coinsSize, int amount){
    memset(visit, 0, sizeof(int) * 10001);
    return coin_amount(coins, coinsSize, amount);   
}

해결 DP bottom up

최종 amount 를 위한 동전들의 최소갯수와 최종 amount값에서 각각의 코인값을 뺀 값의 최소갯수가 계속 중복되는 형태이기 때문에 DP로 풀이가 가능하다. 이를 활용해 점화식을 구하면 아래와 같다.

 f(n) = min( f(n - coins[0]), f(n - coins[1]), ... f(n - coins[k]) ) + 1

만약 값이 [1,2,5] 라고 주어졌을때 3의 경우는 어떻게 구해야하지? 고민을 했고, 처음에는 다른 점화식을 사용해야한다고 생각해서 앞에서 따로 계산하려고 했다. 그래서 답이 안나왔다. 어쨋든 잘못된 방법이고. 점화식을 잘 세웠다면 첫번째 값부터 그 점화식으로 계산이 될것이다. 따라서 3의경우도 이 점화식으로 계산이 된다.

피보나치 수열같이 초기값들을 직접 계산할수 있는경우가 아니라면 항상 첫번째 값부터 점화식으로 계산하면 된다!

// [1,2,5]
// f(11) = min(f(11-1), f(11-2), f(11-5)) + 1;
// f(0) = 0
// f(1) = 1 = min( f(1-1), f(1-2), f(1-5)) + 1
// f(2) = 1 = min( f(2-1), f(2-2), f(2-5)) + 1
// f(3) = 2 = min( f(3-1), f(3-2), f(3-5)) + 1
// f(4) = 2 = min( f(4-1), f(4-2), f(4-5)) + 1

int coinChange(int* coins, int coinsSize, int amount){
    int *sum = (int *)calloc(amount + 1, sizeof(int));
    
    for (int i = 1; i <= amount; i++) {
        int min = INT_MAX;
        int val = 0;
        for (int c = 0; c < coinsSize; c++) {
            val = i - coins[c];
            if (val >= 0 && sum[val] != -1 && sum[val] < min)
                min = sum[val];
        }
        if (min == INT_MAX)
            sum[i] = -1;
        else
            sum[i] = min + 1;       
    }
    return sum[amount];
}