[백준] 9084번 : 동전 (파이썬)

Algorithm/DP

[백준] 9084번 : 동전 (파이썬)

_은선_ 2024. 2. 18. 14:56

SMALL

DP 문제

https://www.acmicpc.net/problem/9084

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

www.acmicpc.net

💡 풀이 코드

import sys
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    c = list(map(int, sys.stdin.readline().split()))
    price = int(sys.stdin.readline())
    dp = [[0] * (price + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        dp[i][0] = 1

    def coin(n, c, price):
        for i in range(1, n + 1):
            for j in range(1, price + 1):
                if j - c[i - 1] < 0 : coinComb = 0
                else: coinComb = dp[i][j - c[i - 1]]
                dp[i][j] = dp[i - 1][j] + coinComb
                
    coin(n, c, price)
    print(dp[n][price])

LIST

저작자표시