목차

동전

ps
링크acmicpc.net/…
출처BOJ
문제 번호9084
문제명동전
레벨골드 5
분류

DP

시간복잡도O(Tnm)
인풋사이즈T<=10, n<=20, m<=10000
사용한 언어Python
제출기록31256KB / 52ms
최고기록48ms
해결날짜2023/09/13

풀이

코드

"""Solution code for "BOJ 9084. 동전".

- Problem link: https://www.acmicpc.net/problem/9084
- Solution link: http://www.teferi.net/ps/problems/boj/9084

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 = [0] * (M + 1)
        dp[0] = 1
        for coin in coins:
            for i, dp_prev in zip(range(coin, M + 1), dp):
                dp[i] += dp_prev

        print(dp[M])


if __name__ == '__main__':
    main()

,