백준 9084 | 동전 (다이나믹 프로그래밍)

문제 출처 : https://www.acmicpc.net/problem/9084

문제

• 우리나라 화페, 특히 동전의 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있다.
• 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다.
• (1원짜리 30개) 또는 (10원짜리 2개와 5원짜리 2개) 등의 방법이 가능하다.
• 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램 작성

입력

• t : 테스트 케이스 개수
• n : 동전의 가지수 (1<=n<=20)
  • 동전의 각 금액이 오름차순으로 정렬되어 주어짐 (1 원 <=Cn <=10000 원)
• m : 동전으로 만들어야 하는 금액 ( 1<=m<=10000 )

문제 접근 방법

• dp index: 가격
• dp[index]: 만들 수 있는 경우의 수

코드

def solution(price: int):
    dp = [0] * (price + 1)
    dp[0] = 1

    for coin in coin_list:
        for i in range(price + 1):
            if i >= coin:
                dp[i] += dp[i - coin]
    print(dp[price])


T = int(input())

for _ in range(T):
    N = int(input())
    coin_list = list(map(int, input().split()))
    solution(int(input()))