https://www.acmicpc.net/problem/9084
시간 1초, 메모리 128MB
input :
- T(1 ≤ T ≤ 10)
- N(1 ≤ N ≤ 20)
- M(1 ≤ M ≤ 10000)
output :
- N가지 동전으로 금액 M을 만드는 모든 방법의 수
코포 문제를 보다가 냅색을 사용해야하는 경우가 발생해 복습 삼아 문제를 풀어 봤다.
동전의 종류를 입력 받기 때문에 이 경우를 다 생각해 주어야 하는데 이럴 때는 DP를 사용해 주어야 한다.
https://velog.io/@jsin2475/BOJ-2293-%EB%8F%99%EC%A0%84-1
과거 문제 중 동일한 알고리즘을 사용한 문제로 동전을 지정해 줬다는 것이 다르다.
예를 들어
2
1 2
1000
이 입력 되었을 때
연산
각 코인마다 해당하는 금액을 만들 수 있는 방법을 저장하고 있어야 한다.
이를 이용해서 내가 i원을 만들려 할 때 i - j가 존재한다면 dp[i] += dp[i - j]를 통해 누적 하여 연산하도록 한다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
coin = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline())
ans = [0] * 10001
ans[0] = 1
for item in coin:
for j in range(1, 10001):
if j >= item:
ans[j] += ans[j - item]
print(ans[target])
