[ BOJ 3067 ] Coins(Python)

문제

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

N가지의 동전 종류가 주어질 때, M원을 만들 수 있는 방법의 수를 구하면 된다.
dp와 그리디 알고리즘을 비교할 때 자주 등장하는 전형적인 문제라고 한다.

문제 풀이

0. 입력 받기

n = int(input())
coins = list(map(int, input().rsplit()))
want = int(input())

1. dp 배열 정의하기

dp = [0 for _ in range(want+1)]
dp[0] = 1

dp[i] = i원 동전을 이용해서 만들 수 있는 방법의 수

0원은 0가지 동전으로 만들 수 있으므로 1가지 방법 뿐이다.
따라서 dp[0] = 1

2. 동전의 종류를 고려해서 dp 할당하기

for i in range(n):
   for j in range(coins[i], want+1):
      dp[j] += dp[j - coins[i]]

동전 종류가 [1, 2, 3]와 같을 때 6원 을 만드는 방법을 생각해보자

i = 0, j = 1~6, coins[i] = 1 일 때

dp[1] += dp[1-1]
dp[2] += dp[2-1]
dp[3] += dp[3-1] ...

i / j	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
0	1	1	1	1	1	1	1

---

i = 1, j = 2~6, coins[i] = 2 일 때

dp[2] += dp[2-2]
dp[3] += dp[3-2]
dp[4] += dp[4-2] ...

i / j	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
0	1	1	1	1	1	1	1
1	1	1	2	2	3	3	4

---

i = 2, j = 3~6, coins[i] = 3 일 때

dp[3] += dp[3-3]
dp[4] += dp[4-3]
dp[5] += dp[5-3] ...

i / j	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
0	1	1	1	1	1	1	1
1	1	1	2	2	3	3	4
2	1	1	2	3	4	5	7

dp[6] 을 출력하면 된다.

코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    coins = list(map(int, input().rsplit()))
    want = int(input())

    # dp[i] = i원 동전을 이용해 j원을 만들 수 있는 경우의 수
    dp = [0 for _ in range(want+1)]
    dp[0] = 1

    for i in range(n):
        for j in range(coins[i], want+1):
            dp[j] += dp[j-coins[i]]

    print(dp[want])