문제 개요
₹1, ₹2, ₹5, ₹10 네 가지 액면가의 동전이 각각 제한된 수량만 있다고 가정해 봅시다. 이 동전들을 조합하여 정확히 ₹n을 만들 수 있는 방법이 총 몇 가지인지 구하는 것이 이번 문제의 목표입니다. 각 액면가별 보유 수량은 크기 4의 배열 count에 담겨 있으며, count[0]은 ₹1 동전의 개수, count[1]은 ₹2 동전의 개수를 나타내는 식입니다.
예를 들어 n = 25이고 count = [7, 3, 2, 2]라면, 즉 ₹1 동전 7개, ₹2 동전 3개, ₹5 동전 2개, ₹10 동전 2개를 가지고 ₹25를 만들어야 할 때 정답은 9가지 방법이 됩니다.
풀이 접근 방식
이 문제는 동적 계획법(DP)의 누적 합산 원리를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 액면가가 작은 동전부터 순서대로 처리하면서, 각 단계에서 이전 단계의 결과를 확장해 나가는 것입니다. 알고리즘의 단계는 다음과 같습니다.
- denom := [1, 2, 5, 10]으로 액면가 배열을 초기화합니다.
- A := 크기가 (n + 1)인 배열을 만들고 모든 요소를 0으로 채웁니다.
- B := A를 복사한 새로운 리스트를 생성합니다.
- i를 0부터 min(count[0], n)까지 반복하면서 A[i] := 1로 설정합니다. 이는 ₹1 동전만 사용해서 만들 수 있는 금액을 표시하는 과정입니다.
- i를 1부터 3까지 반복하며 나머지 액면가(₹2, ₹5, ₹10)를 차례로 처리합니다.
- j를 0부터 count[i]까지 반복하며 해당 액면가의 동전을 j개 사용하는 경우를 고려합니다.
- k를 0부터 (n + 1 - j * denom[i])까지 반복하면서 B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]로 결과를 누적합니다.
- 각 액면가 처리가 끝나면 j를 0부터 n까지 반복하며 A[j] := B[j], B[j] := 0으로 갱신하여 A에 결과를 반영하고 B를 초기화합니다.
모든 액면가에 대한 처리가 완료되면 A[n]을 반환하면 됩니다. 이 값이 정확히 ₹n을 만들 수 있는 서로 다른 조합의 총 개수입니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작 방식을 더 자세히 이해해 보겠습니다.
denom = [1,2,5,10]
def solve(n, count):
A = [0] * (n + 1)
B = list(A)
for i in range(min(count[0], n) + 1):
A[i] = 1
for i in range(1, 4):
for j in range(0, count[i] + 1):
for k in range(n + 1 - j * denom[i]):
B[k + j * denom[i]] += A[k]
for j in range(0, n + 1):
A[j] = B[j]
B[j] = 0
return A[n]
n = 25
count = [7,3,2,2]
print(solve(n, count))입력
25, [7,3,2,2]
출력
9
동작 원리 요약
배열 A는 현재까지 처리한 액면가의 동전들만 사용하여 각 금액을 만들 수 있는 경우의 수를 저장합니다. 새로운 액면가가 추가될 때마다, 그 동전을 0개부터 최대 보유 수량까지 각각 더했을 때 도달 가능한 금액들의 경우의 수를 B에 누적한 뒤 다시 A로 옮기는 방식입니다. 이렇게 하면 동전의 사용 순서는 고려하지 않으면서 조합만 정확하게 계산할 수 있습니다.