문제 설명
서로 다른 액면가(1, 5, 10, 25)의 동전과 총 금액(amount)이 주어졌을 때, 그 금액을 정확히 만들기 위해 필요한 최소 동전 개수를 계산하는 함수를 정의해야 합니다.
예를 들어 입력값이 64라면 출력은 7입니다. 이는 25 + 25 + 10 + 1 + 1 + 1 + 1 = 64처럼 동전 7개로 금액을 구성할 수 있기 때문입니다.
해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 작은 금액부터 차례대로 최소 동전 개수를 계산해 나가고, 그 결과를 dp 배열에 저장하는 것입니다. 알고리즘의 단계는 다음과 같습니다.
- 금액이 0이면 0을 반환합니다.
- 동전 배열의 최솟값이 목표 금액보다 크면 어떤 조합으로도 만들 수 없으므로 -1을 반환합니다.
- 크기가 amount + 1인 dp 배열을 정의하고 모든 값을 -1로 초기화합니다. (-1은 아직 계산되지 않았거나 만들 수 없는 금액을 의미합니다.)
- 동전 배열의 각 동전 i에 대해 다음을 반복합니다.
- i가 dp 배열의 마지막 인덱스(len(dp) - 1)보다 크면 해당 동전은 사용할 수 없으므로 다음 반복으로 건너뜁니다.
- dp[i]를 1로 설정합니다. (동전 하나로 i 금액을 바로 만들 수 있습니다.)
- 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]를 반환합니다. 이 값이 곧 목표 금액을 만드는 데 필요한 최소 동전 개수입니다.
구현 예제
아래는 위 알고리즘을 Python으로 구현한 코드입니다.
class Solution(object): def coinChange(self, amount): coins = [1,5,10,25] 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(64))
입력
64
출력
7
정리
이 방식은 각 금액별 최소 동전 개수를 한 번씩만 계산하므로, 시간 복잡도는 O(amount × 동전 종류 수)입니다. 단순히 큰 동전부터 우선적으로 사용하는 탐욕(Greedy) 방식과 달리, 동적 계획법은 동전 조합이 항상 최적임을 보장한다는 장점이 있습니다.