LeetCode (C/C++) 322. Coin Change

---

풀이

DP 사용, 현재 가격에 대해 동전을 사용할 수 있는 상태라면 값을 갱신

---

코드

class Solution {
private:
    #define MAX_VAL 100000
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end());
        int cnt[10001];

        // 최대 값으로 초기화
        fill(cnt, cnt + 10001, MAX_VAL);

        cnt[0] = 0;
        for (int i = 0; i < coins.size(); i++) {
            int coin = coins[i];

            for (int j = 1; j <= amount; j++) {
                
                // 현재 동전 < 현재 가격이라면 값 갱신
                if (coin <= j)
                    cnt[j] = min(cnt[j], cnt[j - coin] + 1);
            }
        }
        return cnt[amount] != MAX_VAL ? cnt[amount] : -1;
    }
};