동전 짤을 찾기가 힘들어서 계속 도지코인 사진만 올리게 되네요 허

생각해봅시다!!

• 다른 동전 문제를 푼지 얼마 안 된 것 같은데 또 동전이네요... 왜 자꾸 동전은 절 괴롭히는 건지...
• 이번에는 동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세야 합니다.
• 점화식을 바로 떠올리는 건 늘 그랬듯이 어려워요. 예제를 가지고 생각해봅시다.

DP 테이블 정의하기

• 이번에는 DP 테이블로 리스트 coins를 정의합니다.
• coins[i]는 i원을 주어진 동전으로 만들 수 있는 경우의 수를 뜻합니다.
• 본 글에서는 DP 테이블을 이용해, 1, 5, 10원으로 10원을 만들 수 있는 방법의 수를 구해보겠습니다.
• 사용 가능한 동전의 종류를 하나씩 추가해나가며, 다음과 같은 순서로 DP 테이블을 갱신합니다.
  • 1원이 있을 때 -> 1 / 5원이 있을 때 -> 1 / 5 / 10원이 있을 때
  • 순서대로 동전을 추가하는 이유는, 동전의 순서를 고려하지 않기 위해서입니다.
  • 예를 들어서, 1원 + 1원 + 5원과 5원 + 1원 + 1원은 같은 경우로 계산됩니다.

테이블 초기화

i	0	1	2	3	4	5	6	7	8	9	10
coins[i]	1	0	0	0	0	0	0	0	0	0	0

• 처음엔 동전이 하나도 없다고 가정합니다.
• 0원을 만드는 경우는, 아무 동전도 사용하지 않는 1가지 방법이 있으니 coins[0] = 1입니다.
• 나머지 값은, 동전이 없어 금액을 만들 수 없으니 모두 0으로 초기화됩니다.

1단계) 1원이 있을 때

i	0	1	2	3	4	5	6	7	8	9	10
1원 사용 전 coins[i]	1	0	0	0	0	0	0	0	0	0	0
1원 사용 후 coins[i]	1	1	1	1	1	1	1	1	1	1	1

• i + 1원을 만들 때, i원을 만드는 모든 경우에 1원 동전 하나를 추가하면 됩니다.
  • 이렇게 금액을 만드는 경우의 수를, 기존 경우의 수에 추가합니다.
• 따라서 각 i에 대해 coins[i + 1] += coins[i]로 갱신할 수 있습니다.
  • i = 0일 때 coins[1] += coins[0] -> coins[1] = 1 + 0 = 1로 갱신.
  • i = 1일 때 coins[2] += coins[1] -> coins[2] = 1 + 0 = 1로 갱신. 이때 coins[1]의 값이 기존의 0이 아니라, 앞서 갱신된 1임에 유의하세요.
  • ....
  • i = 9일 때 coins[10] += coins[9] -> coins[10] = 1 + 0 = 1로 갱신.
  • i > 9부턴 i + 1 > 10으로 범위를 벗어나니 갱신하지 않음.
• 이러면 coins[10] = 1이 됩니다.
  • 1원을 10개 사용하는 경우를 확인했습니다.

2단계) 1, 5원이 있을 때

i	0	1	2	3	4	5	6	7	8	9	10
5원 사용 전 coins[i]	1	1	1	1	1	1	1	1	1	1	1
5원 사용 후 coins[i]	1	1	1	1	1	2	2	2	2	2	3

• i + 5원을 만들 때, i원을 만드는 모든 경우에 5원 동전 하나를 추가할 수 있습니다.
  • 이렇게 금액을 만드는 경우의 수를, 기존 경우의 수에 추가합니다.
• 따라서 각 i에 대해 coins[i + 5] += coins[i]로 갱신할 수 있습니다.
  • i = 0일 때 coins[5] += coins[0] -> coins[5] = 1 + 1 = 2로 갱신.
  • i = 1일 때 coins[6] += coins[1] -> coins[6] = 1 + 1 = 2로 갱신.
  • ....
  • i = 5일 때 coins[10] += coins[5] -> coins[10] = 1 + 2 = 3으로 갱신. 이때 coins[5]의 값이 기존의 1이 아니라, 앞서 갱신된 2임에 유의하세요.
  • i > 5부턴 i + 5 > 10으로 범위를 벗어나니 갱신하지 않음.
• coins[i]를 더할 때, 매 차례 갱신된 값을 더해야 함에 유의하세요.
• 이러면 coins[10] = 3이 됩니다.
  • 5원을 2개 사용하는 경우, 5원을 1개 / 1원을 5개 사용하는 경우를 새로 확인했습니다.

3단계) 1, 5원, 10원이 있을 때

i	0	1	2	3	4	5	6	7	8	9	10
10원 사용 전 coins[i]	1	1	1	1	1	2	2	2	2	2	3
10원 사용 후 coins[i]	1	1	1	1	1	2	2	2	2	2	4

• i + 10원을 만들 때, i원을 만드는 모든 경우에 10원 동전 하나를 추가할 수 있습니다.
  • 이렇게 금액을 만드는 경우의 수를, 기존 경우의 수에 추가합니다.
• 따라서 각 i에 대해 coins[i + 10] += coins[i]으로 갱신할 수 있습니다.
  • i = 0일 때 coins[10] += coins[0] -> coins[10] = 3 + 1 = 4로 갱신.
  • i > 0부턴 i + 10 > 10으로 범위를 벗어나니 갱신하지 않음.
• 이러면 coins[10] = 4가 됩니다.
  • 10원을 1개 사용하는 경우를 새로 확인했습니다.

점화식

• 즉 M원을 만드는 문제에서 k의 단위를 가진 동전을 확인할 때
• i + k <= M을 만족하는 각 i에 대해
  • coins[i + k] += coins[i]로 갱신해 주면 됩니다.
  • k원 동전을 새로 사용하는 경우, i원을 만드는 모든 경우에 k원을 추가해 i + k원을 만듭니다.
  • 이게 쉽게 떠오를 리가 있나...

풀이

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    # 동전 단위의 수
    N = int(input())
    values = list(map(int, input().split()))
    
    # 만들고자 하는 금액
    M = int(input())
    
    # coins[i]: i원을 만들 수 있는 경우의 수를 저장하는 리스트
    coins = [0] * (M + 1)
    coins[0] = 1	# 0원을 만들 땐 아무 동전을 안 쓰는 1개의 경우 존재
    
    # k의 단위를 가진 동전을 확인하면서, 경우의 수를 갱신
    for k in values:
        for i in range(M + 1):
            # 금액 i + k를 만들기 위해, 이전 금액 i에서 k를 추가
            if i + k <= M:
                coins[i + k] += coins[i]

	# M원을 만들 수 있는 경우의 수 출력
    print(coins[M])

시간 복잡도

• 0원부터 $M$원까지 계산하는 과정에서 $O(M)$.
• 이 과정을 동전 단위의 수 $N$개만큼 반복하므로, $O(N \times M)$.
• 테스트 케이스가 총 $T$개이므로, 최종 $O(T \times N \times M)$.
• $T \leq 10, N \leq 20, M \leq 10,000$이므로 최대 $2,000,000$번 계산
• 이정도면 1초 내 가능.