[백준 9084번] 동전 (python)

문제

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

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

 

기록

(dp 9일차) 동전의 조합 순서가 엇갈리면 여러개로 세어질 수 있기 때문에 (ex. 1+1+2 = 2+1+1) 동전 순차적으로 반복문 돌면서 방법개수를 갱신해나가야한다. 

 

코드

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
    for coin in coins:
        for i in range(coin, M+1):
            if dp[i-coin] : dp[i] += dp[i-coin]
    print(dp[M])

1. 각 n원을 만드는 방법의 개수를 저장할 dp 배열 생성

2. coin을 순차적으로 각 n원마다 경우의 수를 갱신해나간다.

3. M원을 만드는 방법의 개수를 출력한다.