#129 백준 파이썬 [2293] 동전 1 - 점화식

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

 

#Solution

result[10]은 결국 result[9] + result[8] + result[5]의 값이다. 피보나치 수열과 같은 점화식이며 다이나믹 프로그래밍으로 풀어야 시간을 줄일 수 있다.

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

coin_list = []
for _ in range(n):
    coin_list.append(int(input()))

result = [0 for _ in range(k+1)]
result[0] = 1
for i in coin_list:
    for j in range(i, k + 1):
        result[j] += result[j-i]

print(result[k])