[백준] Coins

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

3067번: Coins

냅색문제입니다. dp[i][j]를 i번째 동전을 사용하지 않고 j원을 만들 수 있는 경우와 i번째 동전을 사용하여 j원을 만들 수 있는 경우 두가지로 나누어서 생각하면 풀이할 수 있습니다.

import sys

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    coins = [0] + list(map(int, input().split()))
    # 만들고자 하는 액수
    m = int(input())

    dp = [
        [0] * (m + 1)
        for _ in range(n + 1)
    ]
    # 동전을 쓰지 않고 0을 만들 수 있으므로
    dp[0][0] = 1

    for i in range(1, n + 1):
        for j in range(m + 1):
            # 현재 동전을 추가하지 않고 만들 수 있는 경우
            dp[i][j] = dp[i - 1][j]

            # 현재 동전을 추가하여 만들 수 있는 경우
            if j >= coins[i]:
                dp[i][j] += dp[i][j - coins[i]]
    print(dp[n][m])