[Python] 백준 9084 동전

https://www.acmicpc.net/problem/9084

9084번: 동전

1. 배낭 문제이다. 점화식은 현재까지 가능한 개수에 현재 동전을빼준값에 가능한 개수를 더한다.

dp[i] = dp [i] + dp [j-x]이다.

T = int(input())

while T:
    T -= 1
    n = int(input())
    coin = [0] + list(map(int, input().split()))
    goal = int(input())
    dp = [0 for _ in range(goal+1)]
    dp[0] = 1
    for i in range(1, n+1):
        for j in range(coin[i], goal+1):
            dp[j] += dp[j-coin[i]]

    print(dp[goal])