문제

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

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

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

t = int(input())
for _ in range(t):
    n = int(input())
    coin = sorted(list(map(int, input().split())))
    money = int(input())
    knapsack = [[0] * (money+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        wi = coin[i-1]
        if wi <= money:
            knapsack[i][wi] = 1
            
        for j in range(money+1):
            
            if wi > j and i > 1:
                knapsack[i][j] = knapsack[i-1][j]
            else:
                value = 0
                if j-wi >= 0:
                    value = (knapsack[i][j-wi] + knapsack[i-1][j])
                knapsack[i][j] += value      
                
    print(knapsack[n][money])

백준 9084 동전