[백준/BOJ] 9084 - 동전

9084 - 동전

문제

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

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

코드

def solve():
    N = int(input())
    coin = [int(x) for x in input().split()]
    coin = [0] + coin
    money = int(input())

    dp = [[0 for _ in range(money+1)] for _ in range(N+1)]
    for i in range(len(dp)):
        dp[i][0] = 1

    for i in range(1, N+1):
        for j in range(1, money+1):
            if coin[i] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j] + dp[i][j-coin[i]])
            else:
                dp[i][j] = dp[i-1][j]

    print(dp[N][money])


T = int(input())
for _ in range(T):
    solve()

한마디

바로 전 1535번 안녕 문제와 똑같은 유형이다.

9084번: 동전