[LeetCode] 322 - Coin Change

문제

• 링크: https://leetcode.com/problems/coin-change
• 난이도: Medium
• 태그: 배열, 다이내믹 프로그래밍
• 결과: Time: 26 ms (60.64%), Space: 18.80 MB (58.11%)

풀이

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1)
        {
            return 0;
        }

        vector<int> v(amount);
        return solve(coins, amount, v);
    }

    int solve(vector<int>& coins, int amount, vector<int>& count)
    {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        if (count[amount - 1] != 0) return count[amount - 1];

        int min = INT_MAX;
        for (int coin : coins) 
        {
            int res = solve(coins, amount - coin, count); // coin을 사용
            if (res >= 0 && res < min) // 결과가 유효하고 현재 최솟값보다 작으면 업데이트
            {
                min = res + 1; // coin 1개를 사용했으므로 1 더함
            }
        }

        count[amount - 1] = (min == INT_MAX) ? -1 : min;
        return count[amount - 1];
  }
};

그리디로 풀 수 없다는 사실을 알고 있는데도 어려웠다. 동전 교환 문제를 반드시 그리디로 풀 수 있는 것은 아니므로, 이 문제에서 그리디를 사용하는 풀이는 처음부터 생각하지 않았다. 하지만 그 대안은 무엇인지 생각하기가 어려웠다.

그리고 댓글을 통해 다이내믹 프로그래밍을 통해 풀이해야한다는 사실을 알게 됐는데도 풀이를 전혀 생각해내지 못했다. 문제를 풀다가 이런 순간이 가장 절망스럽다. 첫 발도 디디지 못한 순간!

결국 Editorial 코드를 참고했다.

금액 $S$를 만들기 위해 필요한 최소 동전 개수를 $F(S)$, 마지막으로 사용한 동전의 액수(권종, denomination)를 $C$라고 하자. 그러면 아래 방정식이 성립한다. \(F(S)=F(S-C)+1\) 그런데 우리는 마지막으로 사용한 동전의 액수 $C$를 알지 못하므로 모두 시도해보면 된다. coins에서 하나의 coin을 골라 마지막에 사용한 걸로 가정해보면서 답을 찾아나가면 된다.

배운 점과 후기

DP로 풀이해야한다는 사실을 알고도…

이 문제를 어떻게 작은 문제로 쪼갤 수 있지?

이 고민을 스스로 해결하지 못했다. 개인적으로 DP가 항상 어려워서, DP 문제집을 풀어봐야겠다는 생각이 든다.

이 포스트는 달레 스터디(4주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.