n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
'''logic
"점화식"
1. dp테이블
2. n원을 만들 수 있는 경우의 수는 이전 행의 n원을 만들 수 있는 경우의 수와
n원에서 현재 동전의 가치 k원을 뺀 가치의 경우의 수의 합으로 이루어짐.
==> dp[n] = dp[n] + dp[n-k] (if n-k >= 0)'''
n, k = map(int, input().split())
coin = list(int(input()) for i in range(n))
dp = [0 for _ in range(k+1)]
dp[0] = 1
for i in coin:
for j in range(i, k+1):
if (j-i) >= 0:
dp[j] += dp[j-i]
print(dp[k])
dp문제는 점화식 세우기가 8할인듯 !