[백준 2293 동전 1, 9084 동전 문제] PYTHON

 

9084 문제와 2293 문제는 거의 동일하다.

다른 점은 input을 받는 방식과, 9084는 여러 case들이 주어진 다는 점이다.

따라서 9084 문제를 풀 수 있으면 둘 다 풀 수 있다.

아래는 9084 문제의 풀이이다.

 

동전 문제를 푸는 법은 0원부터 목표 가격까지 1원 단위로 배열로 만들어 

해당 가격을 만들 수 있는 방법의 수를 저장한다.

그 후 dp[k]+=dp[k-c] 로 배열을 늘려가면 문제를 풀 수 있다.

 

T = int(input())
for i in range(T):
    N = int(input())
    Clist = list(map(int, input().split()))
    target = int(input())
    dp = [0 for _ in range(target+1)]
    dp[0] = 1
    for c in Clist:
        for k in range(1, target+1):
            if k-c >= 0:
                dp[k] += dp[k-c]
    print(dp[target])