백준 2293. 동전 1

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

2293번: 동전 1

n, k = map(int, input().split())

coins = [int(input()) for i in range(n)]

dp = [0] * (k + 1)
dp[0] = 1 # 하나의 동전으로만 목표 수 채우는 경우의 수 1
for c in coins:
    for i in range(c, k + 1): # c부터 시작해서 k까지
        dp[i] += dp[i - c] # dp[i-c]에 c인 코인 하나만 더하면 되므로

print(dp[k])

점화식 구하는 거 너무 어렵다...