[ leetcode 문제풀이 ] Coin Change

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

Coin Change - LeetCode

(Coin Change 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Coin Change 문제 설명 >

 

Coin Change 문제는 다음과 같다.

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.

 

다양한 금액의 동전을 나타내는 정수 배열 coins와 총 금액을 나타내는 정수 amount가 주어진다. amount를 채우기 위해 필요한 동전의 가장 적은 수를 리턴하여라. 만약 그 금액이 어떤 동전의 조합으로도 만들어질 수 없다면 -1을 리턴하여라. 각각의 동전의 수는 무한하다고 생각할 수 있다.

 

다음 세 가지 출력 예시가 주어졌다.

주어진 제한 조건은 1 ≤ coins.length ≤ 12, 1 ≤ coins[i] ≤ 2^31 - 1, 0 ≤ amount ≤ 10^4 이다.

 

 

 

---

< Coin Change 문제 접근>

 

완성하고자 하는 함수 coinChange(vector<int>& coins, int amount)에 대한 부분 문제를 생각해보자.

 

위의 1번째 출력 예시로 생각해보면 coinChange(coins, 11)은 coins의 1, 2, 5를 선택한 경우에 대해 각각 coinChange(coins, 10), coinChange(coins, 9), coinChange(coins, 6)을 호출하게 된다. 최종적으로 출력하고자 하는 값이 필요한 coin의 최소 개수이니 호출하는 부분문제에 1을 더한 값의 minimum을 전체 함수의 return 값으로 설정하면 될까? 

 

그렇지 않다. 이렇게 되면 조합할 수 있는 방법이 없을 때 -1을 리턴해야하는 조건에 의해 모든 것이 꼬여버리게 된다. 따라서 필요한 코인의 최소 개수를 저장하는 cache 배열을 방해하지 않고 가능한 코인 조합이 없는 경우의 리턴을 동시에 표현해야 한다.

우선 구현한 코드를 먼저 보자. (Cpp 사용)

int coinChange(vector<int>& coins, int amount) {
    if(amount == 0) return 0;       		//amount가 0인 경우 따로 처리
    vector<int> cache(amount+1);
      
    for(int i=1;i<=amount;i++){      		// 1~amount까지의 부분 문제 memoization
        int ret = 12345;			// amount 최댓값 10^4보다 큰 임의의 값으로 초기화 
        for(int j=0;j<coins.size();j++)
            if(i - coins[j] > 0 && cache[i-coins[j]] != 0){
                ret = min(ret, 1+cache[i-coins[j]]);
                continue;
            }
            else if(i - coins[j] == 0)
                ret  = 1;
        if(ret == 12345) ret = 0;		// 한 번도 조건문을 만족하지 못한 경우 가능한 조합 수 0
        cache[i] = ret;
    }
    if(cache[amount] == 0) return -1;		// 가능한 조합 수가 0 인 경우(amount가 0인 경우와 다른 case)
    else return cache[amount];
}

부분 문제에 대해 가능한 코인의 조합이 없는 경우 리턴해야 하는 값인 -1로 메모이제이션을 할 경우 min연산에 대해 가능한 다른 어떤 조합으로 나오는 결과보다 작기에 코드의 동작을 망치게 된다. 따라서, cache[0]을 제외한 다른 모든 경우 가능한 조합의 수가 없으면 cache[i]값에 0을 할당하였다. 만약 부분 문제의 탐색 중 cache[i] (i>0)이 0의 값을 가지면 조건문을 만족하지 못하게 되고 ret = 0;의 할당을 통해 가능한 조합의 수는 가능한 조합끼리 카운트(min 연산을 통해)하고 가능하지 않은 조합은 가능하지 않은 조합대로 메모이제이션이 적용된 것이다. 

 

마지막으로 cache[amount]를 호출했을 때 0의 값을 가지면 이는 가능한 코인 조합이 없다는 뜻이므로 -1을 반환하도록 해주면 되는 것이다. 이 방식으로 amount 입력이 0인 경우와 가능한 코인 조합이 없는 경우의 출력을 구분할 수 있었다.

 

 

문제 풀이에는 성공했지만, Runtime이 별로 좋지는 못해 좀 찜찜하긴 하다...