[9084] 동전 In python

 

> dp

 

윽..

너무 싫어하는 dp 문제다 ㅠㅠ

 

이 문제는 동전의 종류가 주어지고

주어진 금액을 만드는 모든 방법을 세서 출력하는 문제다.

 

 

 

동전의 종류 2, 3, 5원

목표 금액 10원

 

위 예시의 과정을 풀어보기

	1	2	3	4	5	6	7	8	9	10
2원	0	1	0	1	0	1	0	1	0	1
3원	0	1	0+1	1+0	0+1	1+1	0+1	1+1	0+2	1+1
5원	0	1	1	1	1+1	2+0	1+1	2+1	2+1	2+2

 

총 4가지의 방법이 있다.

 

위 과정을 dp 방식으로 코드를 작성하면

아래와 같다

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

 

dp[i]+=dp[i-coin]

이 부분을 구현할 때 좀 어려움을 느낌 ㅠ.ㅠ

규칙을 찾기가....