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