9084 백준 파이썬

동전으로 돈만들기.

 

1,2로 7을 만드는 경우를 살펴보면, 

1+6을 만드는 경우의 수

2+5를 만드는 경우의 수가 있다.

그런데 이걸 1과 2를 동시에 진행시키면 중복되는 경우가 세지게 된다.

그래서 결론적으로는 피보나치수열처럼 된다.

아래는 잘못 작성한 코드이다.

t = int(input())
for i in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    m = int(input())
    dp = [0 for i in range(m + 1)]
    dp[0] = 1
    for x in range(1, m + 1):
        for t in l:
            if x - t >= 0:
                dp[x] += dp[x - t]
    print(dp)

이것을 1과 2의 경우를 분리해서 진행한다면, 중복되는 경우는 세지지 않는다. 따라서 

t = int(input())
for i in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    m = int(input())
    dp = [0 for i in range(m + 1)]
    dp[0] = 1
    for t in l:
        for x in range(1, m + 1):
            if x - t >= 0:
                dp[x] += dp[x - t]
    print(dp[m])