문제

문제 분석

처음엔 Greedy를 생각해보았다.
큰 수를 최대한 많이 넣으면 되지 않을까?
한번 생각해보자.

그러나 아래와 같은 경우 Greedy로 풀 수 없다.
[13, 5, 4, 1] 64
13 13 13 13 5 5 1 1
13 13 13 13 4 4 4

그러면 그냥 Naive로 푼다고 해보자. 이때는 모든 조합을 시도해 보아야 한다.
coin idx와 sum을 매개변수로 Recursive하게 여러 조합을 시도하다 보면 중복이 발생한다.
예를들어, 서로 다른 경우로 들어왔음에도 i번째 coin에서 채워야할 남은 돈이 30원인 경우가 반복적으로 나올 수 있다.

이러한 특성을 이용하면 dp로 풀 수 있을 것이고,
시공간 복잡도도 계산해보면 얼마 안 된다.

알고리즘

DP

자료구조

vector

결과

시간 복잡도: O(amount*coins)
공간 복잡도: O(amount)

class Solution {

const int NA = INT32_MAX;

public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, NA);

        dp[0] = 0;
        for ( int sum = 1; sum <= amount; sum++ ){
            for ( int coin : coins ){
                if ( sum - coin >= 0 && dp[sum-coin] != NA ){
                    dp[sum] = min( dp[sum], dp[sum-coin]+1);
                }
            }
        }

        if ( dp[amount] == NA )
            return -1;
        else
            return dp[amount];
    }
};

Other

처음에는 {sum, coin idx} 두 가지 원소를 축으로 사용했다.
문제가 해결되긴 했으나, 다른 사람보다 시간과 공간 소모가 컸다.

다시 한번 생각해보니, sum 원소 하나만으로도 풀 수 있었다.

Recursive하게 푼다고 하면 축이 두개가 필요했기 때문에 당연히 dp도 2축으로 생각했다.

DP가 가능하겠다 라는 생각이 들었다면, 혹시 축이 덜 또는 더 필요하지 않은지 한번만 검토하고 넘어가는 습관을 들이자.