[백준 9084] 동전 (python)

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

9084번: 동전

동전 문제

동전의 종류가 주어 질 때 주어진 금액을 만드는 모든 방법의 수를 세는 프로그램을 작성하는 문제

 

사용 알고리즘

#다이나믹 프로그래밍

 

📌문제 접근 포인트

1. 동전의 종류가 오름차순으로 주어진다. 해당 동전들로 주어진 금액을 만들어보자.
2. 단순하게 다이나믹 프로그래밍을 구상해보자. 먼저 dp를 구상할때 0원으로 만들 수 있는 경우의 수는 무조건 1이므로 dp[0] = 1이다.
3. 예시를 생각해보자.
2원, 5원 동전으로 10원을 만든다고 가정해보자.
1) 2원만 사용했을 경우, 만들 수 있는 가지 수의 조합은 아래와 같은 표로 작성할 수 있다.

2) 여기서 2원과 5원의 조합으로 만들 수 있는 표를 만들면 다음과 같다.

5원을 사용할 때는, 2원의 상태를 기본베이스로 사용해서 추가를 해야한다. (경우의 수에 포함이 되어있으니)
2원과 5원이 있을 때는 7원(2+5)과, 9원(2+2+5)도 만들 수 있는 경우의 수가 생긴다.

7원을 만들기 위한 경우의 수를 구하기 위해서는 우선 앞에서 2원을 만들 수 있는 경우의 수 dp[2]와 동일하게 구조가 이루어 진다. 이는 dp[(7원 - 5원)]의 위치와 동일하다. 
9원을 만들기 위한 경우의 수를 구하기 위해서는 4원을 만들 수 있는 경우의 수 dp[4]와 동일하게 구조가 이루어진다. 이는 dp[(9원 -5원)]의 위치와 동일하다.
→ 즉, 만들고 싶은 금액을 money라 하면  dp[moeny] = dp[money-coin]의 구조이다. 

위 경우를 보면 현재 동전의 가치가 큰 금액을 만들 경우(money >= coin) 동전의 조합으로 이루어짐을 알 수 있다.
이 방법들을 활용해서 구성해보자.
4. 위 예시에서 만든 구조를 그대로 코드화 하면 성공

⚙ 내가 푼 정답 코드

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N, coins, M = int(sys.stdin.readline()), list(map(int, sys.stdin.readline().split())), int(sys.stdin.readline())
    dp = [0]*(M+1)
    dp[0] = 1 # 0원으로 만드는 가지 수 1개
    for coin in coins:
        for money in range(M+1):
            if money >= coin: # 금액이 동전의 가치보다 크면
                dp[money] += dp[money-coin] # 해당 dp는 금액 - 동전에 해당하는 dp합
    print(dp[M])