[백준] 2293 동전1

DP 문제 입니다.
저는 이런 문제를 풀 때 일반항 세우는 것이 직관적으로 떠오르지 않아서 직접 손으로 쓰면서 이해하는 편입니다.
그래서 10개까지의 항과 동전의 단위를 행렬로 나타내었습니다.

문제 풀이 전략
1. 1, 2, 5 같은 경우는 1이기 때문에 d[0] = 1로 , 나머지는 0으로 초기화
2. d를 구할 때는 동전의 단위보다 클 때만 고려합니다. 왜냐면 그전에는 0이니까!
3. d를 구할 때 쓰는 j가 동전의 단위보다 크다면 ? 규칙을 보면
d[i] = d[j-i] 이렇게 구해집니다.
4. 그리고 동전의 단위를 모두 더해야하므로 d[i] +=d[j-i] 더해서
최종적인 d[k]를 출력합니다~

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
lst = []
for i in range(n):
	lst.append(int(input()))
# print(lst)
'''
  1 2 3 4 5 6 7 8 9 10 
1 1 1 1 1 1 1 1 1 1 1
2 0 1 1 2 2 3 3 4 4 5
5 0 0 0 0 1 1 2 2 3 4
s 1 2 2 3 4 5 6 7 8 10

'''
d = [0] * (k+1)
d[0] = 1
for i in lst:
	for j in range(i, k+1):
		if j >= i:
			d[j] += d[j-i]
print(d[k])