[C++] LeetCode : Coin Change

Question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

다른 단위의 동전을 나타내는 정수 배열 동전과 총금액을 나타내는 정수 금액이 제공됩니다. 해당 금액을 구성하는 데 필요한 가장 적은 수의 동전을 반환합니다. 동전의 어떤 조합으로도 그 금액을 채울 수 없으면 -1을 반환합니다. 각 종류의 동전이 무한히 있다고 가정할 수 있습니다.

제약사항

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 동전의 타입은 알아야 하기 때문에, 동전 타입의 개수를 n이라 하면 O(n)이다

고려사항

---

Solution1 (Dynamic Programming)

점화식을 세우는것이 가장 중요하다. 

각 총 금액의 합에 대하여, 조합할 수 있는 동전 타입은 그 동전 타입 하나를 제외했을 때의 총금액의 합 + 1이다. 

 

예를 들어,  coin의 종류가 1원, 2원, 5원짜리가 있고, 총 금액 합 11원을 만들 때 가능한 조합을 생각해보면

11 = 5 + 5 + 1

11 = 5 + 2 + 2 + 2

11 = 5 + 2 + 2 + 1 + 1

11 = 2 + 2 + 2 + 2 + 2 + 2 + 1

...

 

이런식으로 무수히 많다. 

만약, 11원을 만들 수 있는 조합의 수의 최솟값이 dp [11]이라 한다면,

dp [11]는 6원을 만들 수 있는 조합의 수의 최솟값 dp [6] + 5원짜리 1개로 표현할 수 있다. 또, 

dp [11]는 9원을 만들 수 있는 조합의 수의 최솟값 dp [9] + 2원짜리 1개로 표현할 수 있다. 

 

따라서 점화식은

dp[(목표금액)] = min(dp [동전 하나로 만들 수 있거나, 지금 계산하기 전 가능했던 최소의 조합 수), dp[(목표금액 - 동전의 단위)] + 1)로 나타낼 수 있다.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[10001];
        fill_n(dp, 10001, INT_MAX-1);
        dp[0] = 0;
        
        for(int i=0; i<coins.size(); i++){
            for(int j=coins[i]; j<=amount; j++){
                dp[j] = min(dp[j], dp[j-coins[i]] + 1);
            }
        }
        
        if(dp[amount] == INT_MAX-1) return -1;
        return dp[amount];
    }
};

• Time complexity : O(cn) // c는 동전의 종류, n는 목표 금액 
• Space Complexity : O(n) 

출처 : Explore - LeetCode

Explore - LeetCode