백준 2293 동전 1

20.32m

나의 답

import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
coins = [int(input().rstrip()) for _ in range(n)]
dp = [0] * (k + 1)
dp[0] = 1

for coin in coins:
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

print(dp[k])

점화식이 감도 안와서 결국 아이디어를 검색으로... ㅠ
다시 한 번 풀어봐야겠다.