문제 개요
서로 다른 액면가를 가진 여러 종류의 동전과 목표 금액(amount)이 주어졌을 때, 이 금액을 정확히 만들기 위해 필요한 동전의 최소 개수를 계산하는 함수를 작성해야 합니다. 만약 어떤 조합으로도 해당 금액을 만들 수 없다면 -1을 반환합니다.
예를 들어 동전 종류가 [1, 2, 5]이고 목표 금액이 11이라면 정답은 3입니다. 5 + 5 + 1 = 11처럼 세 개의 동전으로 금액을 구성할 수 있기 때문입니다.
해결 접근 방법: 동적 계획법(DP)
이 문제는 대표적인 동적 계획법(Dynamic Programming) 유형입니다. 핵심 아이디어는 각 금액 k에 대해 그 금액을 만드는 데 필요한 최소 동전 개수를 dp[k]에 저장하고, 이미 구한 작은 금액의 답을 재활용하여 점차 큰 금액의 답을 구해 나가는 것입니다.
알고리즘 단계
- amount가 0이면 0을 반환합니다.
- coins 배열의 최솟값이 amount보다 크면 -1을 반환합니다.
- 크기가 amount + 1인 배열 dp를 선언하고 모든 값을 -1로 초기화합니다. (-1은 아직 해당 금액을 만들 수 없음을 의미합니다.)
- coins 배열의 각 동전 i에 대해 다음을 수행합니다.
- i가 dp 배열의 마지막 인덱스보다 크면 해당 동전은 사용할 수 없으므로 다음 반복으로 건너뜁니다.
- dp[i]를 1로 설정합니다. (동전 하나로 즉시 만들 수 있는 금액)
- j를 i + 1부터 amount까지 반복하면서:
- dp[j - i]가 -1이면, 즉 (j - i) 금액을 만들 수 없다면 건너뜁니다.
- dp[j]가 아직 -1이라면 dp[j] = dp[j - i] + 1로 갱신합니다.
- 그렇지 않다면 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)
#print(dp)
return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5], 11))입력
[1,2,5] 11
출력
3
복잡도 분석
이 알고리즘의 시간 복잡도는 O(amount × 동전 개수)이며, 공간 복잡도는 dp 배열을 위해 O(amount)입니다. 동전 종류가 많거나 금액이 커져도 완전 탐색보다 훨씬 효율적으로 동작하므로, 코딩 테스트에서 자주 등장하는 동전 교환 문제의 표준적인 풀이 방법으로 널리 활용됩니다.