파이썬 백준 9084 동전

testcase = int(input())
for t in range(testcase) : 
    n = int(input())
    C = list(map(int, input().split()))
    m = int(input())
    DP = [0 for i in range(m + C[-1] + 1)]
    DP[0] = 1
    for coin in C : 
        for i in range(1, m + 1) : 
            DP[i] = DP[i] + DP[i - coin]
    print(DP[m])

IDEA

50원, 100원, 500원 동전이 있다고 하자.

5000원을 만드는 경우는, 4500원을 만드는 경우에 500원 하나를 더하거나, 4900원을 만드는 경우에 100원 하나를 더하거나, 4950원을 만드는 경우에 50원 하나를 더하는 것이다.

즉 n원을 만드는 경우의 수는 n-coin원을 만드는 경우의 수들의 합과 같다.

점화식으로 표현하면 아래와 같다.

f(n) = Sigma(coin in C)[f(n-coin)]

 

m만큼의 dp를 만들고, coin중 가장 큰것만큼의 메모리를 더 썼다.

DP[i-coin]이 리스트의 끝에서 역류해 0을 출력하므로 2중for문 안에서 if문을 안쓰겠다는 의도였던것 같다.

컴퓨터는 자원을 더쓰지만 내가 편해졌으니 이득