주어진 동전으로 n 루피를 만드는 조합의 수를 구하는 Python 프로그램

문제 개요

액면가가 1, 2, 5, 10루피인 동전이 주어져 있다고 가정해 보겠습니다. 이 동전들을 사용해 정확히 n루피를 만들 수 있는 조합이 총 몇 가지인지 구해야 합니다. 각 액면가별로 사용할 수 있는 동전의 개수가 담긴 배열 count가 제공되며, count[0]은 1루피 동전의 개수, count[1]은 2루피 동전의 개수를 의미하는 식으로 저장되어 있습니다.

예를 들어 입력이 n = 27, count = [8, 4, 3, 2]라면 출력은 18이 됩니다. 즉, 총 18가지의 조합이 가능하며 그중 일부는 다음과 같습니다.

10×2 + 5×1 + 2×1 = 27
10×2 + 2×3 + 1×1 = 27
10×1 + 5×3 + 2×1 = 27
10×1 + 5×1 + 2×4 + 1×4 = 27

이 외에도 다양한 조합이 존재합니다.

풀이 접근 방법

이 문제는 동적 계획법(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까지 반복하며 나머지 액면가를 차례로 처리합니다.
- 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[n]을 반환합니다.

동작 원리

배열 A의 각 인덱스 k는 "현재까지 고려한 동전으로 k루피를 만드는 방법의 수"를 의미합니다. 처음에는 1루피 동전만 고려하므로, 0부터 min(count[0], n)까지의 금액은 각각 정확히 한 가지 방법(1루피 동전을 해당 금액만큼 사용)으로 만들 수 있습니다.

이후 2루피, 5루피, 10루피 동전을 순서대로 추가하면서, 각 동전을 j개 사용하는 모든 경우를 기존 결과에 더해 누적 계산합니다. B 배열은 새로운 액면가를 반영한 임시 결과를 저장하는 역할을 하며, 액면가 하나의 처리가 끝날 때마다 A로 복사됩니다. 모든 액면가를 처리한 뒤 A[n]이 곧 정답이 됩니다.

이 알고리즘의 시간 복잡도는 O(n × 전체 동전 개수), 공간 복잡도는 O(n)입니다.

예제 코드

아래 구현을 통해 더 자세히 이해해 보겠습니다.

denom = [1,2,5,10]

def solve(n, count):
    A = [0 for _ in range(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 = 27
count = [8,4,3,2]
print(solve(n, count))

입력

27, [8,4,3,2]