서로 다른 액면가의 동전들과 하나의 목표 금액(amount)이 주어졌을 때, 그 금액을 정확히 만들기 위해 필요한 최소 동전 개수를 계산하는 함수를 작성해야 합니다. 만약 어떤 동전 조합으로도 해당 금액을 만들 수 없다면 -1을 반환합니다.
예를 들어 동전 배열이 [1, 2, 5]이고 목표 금액이 64라면, 출력은 14가 됩니다. 이는 12×5 + 2 + 2 = 64, 즉 5원짜리 12개와 2원짜리 2개로 금액을 구성할 수 있기 때문입니다.
문제 해결 접근 방식
이 문제는 대표적인 동적 계획법(Dynamic Programming) 유형으로, 다음 단계에 따라 해결할 수 있습니다.
- 목표 금액이 0이면 필요한 동전 개수도 0이므로 0을 반환합니다.
- 동전 배열의 최솟값이 목표 금액보다 크면 어떤 조합으로도 금액을 만들 수 없으므로 -1을 반환합니다.
- 크기가 amount + 1인 dp 배열을 선언하고 모든 값을 -1로 초기화합니다. 여기서 dp[i]는 금액 i를 만들 때 필요한 최소 동전 개수를 의미하며, -1은 아직 도달 불가능한 상태를 나타냅니다.
- 동전 배열의 각 동전 i에 대해 다음을 수행합니다.
- i가 dp 배열의 인덱스 범위를 벗어나면 다음 반복으로 넘어갑니다.
- dp[i]를 1로 설정합니다(동전 하나로 금액 i를 바로 만들 수 있음).
- j를 i + 1부터 amount까지 순회하며 다음을 확인합니다.
- dp[j - i]가 -1이면 건너뜁니다.
- dp[j]가 아직 -1이라면 dp[j] = dp[j - i] + 1로 갱신합니다.
- 그렇지 않으면 dp[j] = min(dp[j], dp[j - i] + 1)로 더 작은 값을 저장합니다.
- 마지막으로 dp[amount]를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object): def coinChange(self, coins, amount): if amount == 0 : return 0 if min(coins) > amount: return -1 dp = [-1 for i in range(0, amount + 1)] for i in coins: if i > len(dp) - 1: continue dp[i] = 1 for j in range(i + 1, amount + 1): if dp[j - i] == -1: continue elif dp[j] == -1: dp[j] = dp[j - i] + 1 else: dp[j] = min(dp[j], dp[j - i] + 1) return dp[amount] ob1 = Solution() print(ob1.coinChange([1,2,5],64))
입력
[1,2,5], 64
출력
14
정리
이 알고리즘은 각 금액별 최소 동전 개수를 dp 배열에 누적적으로 갱신하는 방식으로 동작합니다. 시간 복잡도는 O(amount × 동전 종류 수)이며, 공간 복잡도는 O(amount)입니다. 이러한 동적 계획법 접근은 완전 탐색에 비해 훨씬 효율적으로 최적해를 구할 수 있다는 장점이 있습니다.