문제

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

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

# 3067
import sys
input = lambda: sys.stdin.readline().strip()

t = int(input())
for _ in range(t):
    n = int(input())
    coin = list(map(int, input().split()))
    m = int(input())
    
    knapsack = [0] * (m+1)
    
    for c in coin:
        if c > m:
            break
        
        knapsack[c] += 1
        
        for j in range(m+1):
            if c > j:
                continue
            else:
                knapsack[j] += knapsack[j-c]
                
    print(knapsack[m])

백준 3067 Coins