알고리즘 - Python / 백준 - 9084번 : 동전

9084번: 동전 (acmicpc.net)

9084번: 동전

 

---

풀이

• DP 알고리즘의 대표적인 문제다.
• 동전이 주어지고 , 그 동전들을 가지고 해당 금액을 만들 수 있는 경우의 수를 구하는 문제다.
• DP 점화식은 DP[I] = DP[I-K] + DP[I] 로 I 금액을 K 금액의 동전으로 만드는 경우를 이야기한다.
• 만약 1원 2원을 가지고 17원을 만드는 경우는 16원을 만드는 경우에 1원 동전을 사용하는 경우 , 15원을 만드는 경우에 2원 동전을 사용하는 경우 2가지 일 것이다.

 

import sys
n = int(sys.stdin.readline())
for _ in range(n):
    p = int(sys.stdin.readline())
    c = list(map(int, sys.stdin.readline().split(" ")))
    money = int(sys.stdin.readline())
    dp = [0 for i in range(money+1)]
    dp[0] = 1
    for i in c:
        for o in range(1,money+1):
            if o >= i:
                dp[o] = dp[o] + dp[o-i]
    print(dp[money])

---