[python] 백준 9084 동전

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

9084번: 동전

 

문제 해결

• dp[i]는 i원을 만드는데 가지수를 나타내는 것이다.
• 1원부터 $10^{4}$까지 차례로 dp를 통해 나타낸다.
• 동전이 있는것은 1개로 되므로 dp[coin]은 1이상이다.

 

 

CODE

for _ in range(int(input())):
    n = int(input())
    coins = list(map(int, input().split()))
    total = int(input())

    dp = [0]*(total+1)
    dp[0] = 1

    for coin in coins:
        for i in range(total+1):
            if i >= coin:
                dp[i] += dp[i-coin]
    print(dp[total])