릿코드 322. Coin Change 문제에 대한 복기이다.
Naive Approach
이 문제를 풀때, Greedy한 방식으로 풀 생각이 가장 먼저들었다. 금액이 주어지면, 그 금액보다 작은 동전 중에서 가장 큰 동전을 사용하여 액수를 채워 만들 수 해당 금액을 만들 수 있는지 확인하는 방식이다. 하지만 구현하는 도중 바로 뭔가가 잘못됐음을 알았다.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
위와 같은 예제에서는 필자가 생각한 Greedy 방식이 적용된다. 어떻게 보면 함정이라고 볼 수도 있겠다. 하지만 다양한 상상을 해 봤을때, 이 방식이 막히는 경우가 존재했다.
amount = 12
coins = [6,7]
인 경우, 바로 Greedy 방식이 막힌다
아주 간단한 예제만 상상해봐도 막힌다는 것을 알 수 있다.
따라서 DP를 적용해야 할 것이라는 생각은 들었지만, 정확히 어떤 점화식을 도출해내야 되는지 확실하지 않았다.
처음에 생각한 것은 구해야 하는 amount까지 dp 배열을 만들고, 각 코인들의 배수마다 코인을 나눈 수만큼 사용하여 초기화하고, 그 외의 수에서는 초기화된 수들을 조합하여 해당 수가 만들어진지 확인하고, 만들어질 경우 사용하는 것이다. 하지만 딱봐도 시간 초과가 날 것 같은 방식이었다. 지금 생각해보면, 이 방식은 O(nPm!)이 쓰였을것이다. 왜냐하면 n개의 수에서 m가지 종류의 동전들을 사용하는 것이고, 그 방식의 개수는 nPm이다. 또, amount까지는 팩토리얼까지 해줘야 한다. 지금 생각해보면 정말 터무니 없다.
해답
알고보니 DP의 아주 기초적인 문제라고 한다 (그만큼 DP에 약하고, 기초가 부실한것 같다).
각 코인별로 루프를 돌고, dp[i] 와 dp[i-coin]을 비교하여 dp배열을 초기화하는 것이다. 이렇게 할 경우, O(n)의 시간 복잡도를 가진다. 여기서 n은 amount이다.
Constraints:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
위와 같은 제약 사항을 가지고 있기 때문에 최대로는 10^4 * 12회 실행될것이다.
구현한 코드는 다음과 같다.
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
max_amount = amount + 1
dp = [max_amount] * max_amount
dp[0] = 0
for coin in coins:
for i in range(coin, max_amount):
dp[i] = min(dp[i], dp[i-coin] + 1)
if (dp[amount] > amount):
return -1
return dp[amount] 배운점
아직 dp에 대한 기초가 부족하다고 생각이 됐다. 점화식의 경우에는 배우는 것이 아니라 떠올리는 것이고, 여러 종류의 점화식을 접할수록 기억에 남는것이 많을 것이라고 생각한다. 필자도 coin change 문제와 비슷한 문제를 분명히 풀어봤을 것이라 생각하지만, 시간이 지나서 기억이 잘 나지 않았다. 여러 문제를 풀어보는 것도 중요하지만 한 문제를 여러번 풀어보고 확실히 이해하고 내 것으로 만들어야겠다는 생각이 들었다. 또, dp문제를 집중적으로 풀어봐야 될 것 같다.
