[BAEKJOON] 9084 동전 - Python

9084번: 동전 (acmicpc.net)

9084번: 동전

 

 

 

<문제 풀이>

- 각각의 동전들이 1 ~ m원까지 만들 수 있는 곳의 경우의 수를 구한다.

- i-coin을 만드는 값이 존재하는 경우

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

- 존재하지 않는 경우는 그대로 유지

 

 

 

<Code>

import sys
input = sys.stdin.readline


T = int(input())
for _ in range(T):
    n = int(input())    # 동전의 가지수
    coins = list(map(int, input().split()))    # 동전
    m = int(input())    # 금액

    dp = [1] + [0] * m    # dp

    for coin in coins:
        for i in range(m+1):
            if i >= coin:    # 현재 경우의 수(dp[i])에 이전 경우의 수(dp[i-coin])를 더한다.
                dp[i] += dp[i-coin]

    print(dp[m])

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.