백준 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$ 원 $<= C_n <= 10000$ 원 )
• m : 동전으로 만들어야 하는 금액 ( $1 <= m <= 10000$ )

문제 접근 방법

• 동전이 오름차순으로 정렬되어 주어지기 때문에 작은 동전부터 해당 동전을 이용하여 $m$ 원을 만들 수 있는 경우의 수를 더한 뒤, 다음 동전으로 넘어가서 이전 경우의 수에 해당 동전으로 만들 수 있는 경우의 수를 순차적으로 더해가며 답을 구한다.

• $a_i$ : 금액 i를 만드는 방법의 수
• $k$ : 각 화폐의 단위
• 점화식 : 각 화폐의 단위인 $k$를 돌면서 금액 $1$ ~ $M$ 을 만들 수 있는지 확인한다.
  • 1) $a_{i-k}$를 만드는 방법이 존재한다면 ($i >= k$)
    • $a_i$ = $a_i$ + $a_{i-k}$
  • 2) $a_{i-k}$를 만드는 방법이 존재하지 않는다면
    • $a_i$ = $a_i$ (이전의 경우의 수 그대로)

코드

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())

    # memoization을 위한 리스트 선언
    d = [0] * (m + 1)
    d[0] = 1


    for coin in coins:
        for i in range(m + 1):
            # a_(i-k) 를 만드는 방법이 존재한다면 
            # 이전 경우의 수에 현재 동전으로 만들 수 있는 경우의 수를 더한다.
            if i >= coin:
                d[i] += d[i - coin]

    print(d[m])

memoization 예시 필기 노트