동전 - 9084번

문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

입력
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

출력
각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

풀이

다음의 코드는 정답이다.

import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    N = int(input())
    coins = list(map(int, input().split()))
    M = int(input())
    dp = [0]*(M+1)
    if M==1:
        print(1)
    elif M==2:
        print(2)
    else:
        dp[0] = 1
        for c in coins:
            for m in range(c, M+1):
                dp[m] += dp[m - c]
        print(dp[-1])

역시 핵심은 else문 안의 내용이다. 이 부분에 대한 수도코드를 적어보자면 아래와 같을 것이다. 편의상 첫번째 등장하는 for문을 큰 for문, 두번째 등장하는 for문을 작은 for문이라고 칭하겠다.

        for c in coins: 			# 주어진 동전들 중 각 동전들 중 
        							  현재 검사할 동전 c에 대해,
            for m in range(c, M+1): # 이 동전의 가격이 되는 숫자에서부터 
            						  목표가격이 되는 숫자까지가 
                                      우리가 이번 큰 for문 회차에서 수행할 검사의 범위이고, 
                dp[m] += dp[m - c]  # 동전 한 번을 더하면 그 동전의 가격만큼 M에서 빼준 값이 
                					  이 다음 회차의 검사에서의 목표가격이 된다.

작은 for문에서의 작용은 곧 목표 가격까지 이 "현재 동전 c"를 한 번, 두 번, 세 번... 쓸 수 있는 경우의 수를 배열 dp를 통해 기록해놓는 셈이다. 배열 dp의 인덱스값이 우리가 연산해나가고 있는 과정 상의 돈의 크기를 뜻하며, 곧 배열 dp의 맨 끝 원소의 인덱스가 우리의 최종 목표 가격인 것이다.

"현재 동전 c"에 대한 검사(기록)가 끝나면 그 다음 동전 c에 대해 또 똑같이 그 동전을 사용할 수 있는 횟수를 전부 도출해낸다.

그렇게 모든 동전에 대한 경우의 수를 다 기록한 뒤, 최종적으로 맨 끝 원소의 값을 확인하여 우리가 최종 목표하면 그 가격이 몇 번이나 달성되었는가를 알게 된다.