| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 3067 |
| 문제명 | Coins |
| 레벨 | 골드 5 |
| 분류 |
DP |
| 시간복잡도 | O(Tnm) |
| 인풋사이즈 | T<=?, n<=20, m<=10000 |
| 사용한 언어 | Python |
| 제출기록 | 31256KB / 56ms |
| 최고기록 | 56ms |
| 해결날짜 | 2023/09/13 |
"""Solution code for "BOJ 3067. Coins".
- Problem link: https://www.acmicpc.net/problem/3067
- Solution link: http://www.teferi.net/ps/problems/boj/3067
Tags: [DP]
"""
def main():
T = int(input())
for _ in range(T):
N = int(input()) # pylint: disable=unused-variable
coins = [int(x) for x in input().split()]
M = int(input())
dp = [1] + [0] * M
for coin in coins:
for i in range(M - coin + 1):
dp[i + coin] += dp[i]
print(dp[M])
if __name__ == '__main__':
main()