백준 2293(동전 1) - Python(파이썬) - 다이나믹

2293번: 동전 1

풀이방법
① dp[i] : i를 만들 수 있는 경우의 수라고 가정
② 처음부터 n가지 종류의 동전을 하는 것이 아니라 한개부터 n가지의 종류의 동전으로 늘려간다.
③ 동전의 종류를 늘려갈 때 0원부터 시작해서 k원까지 만들 수 있는 경우의 수를 구한다. 
점화식 : dp[j ] = dp[j] +dp[j-i]

ex ]

[ 1 ]로 만들 수 있는 경우의 수는 0원부터 k원까지 1가지 일 것이다.
[ 1,2 ]로 만들 수 있는 경우의 수를 구할 때 6원일 때의 값을 구한다하면 dp[6] = dp[6]+dp[6-2] 
이런식으로 구하는데 왜냐하면 6원은 오직 1원만 가지고 6을 만든 가지수(dp[6]) 4원에서 2를 더하면 6이 만들어지기때문에 dp[4]의 경우 1원과2원을 합쳐서 만든 경우의 수이다. 따라서 이 둘을 더하게 되면 1원만 가지고 만든 경우의 수와 1,2원을 가지고 만든 경우의 수를 모두 가지게 된다. 

이걸 코드로 돌려서 표현을 해보면1) [ 1 ]로 만들 수 있는 경우의 수

2) [ 1,2 ] 로 만들 수 있는 경우의 수

3) [ 1,2,3 ]으로 만들 수 있는 경우의 수

import sys
n,k = map(int,sys.stdin.readline().split())
array=[int(sys.stdin.readline()) for i in range(n)]
array.sort()

dp=[0]*(k+1)
#0을 만들 수 있는 경우의 수는 항상 1개이다-> 아무것도 없을 때 이므로
dp[0]=1

for i in array:
    # k=0일때의 값을 제외해야하므로 range는 1부터 시작한다.
    for j in range(1,k+1):
        if j>=i:
            dp[j]=dp[j]+dp[j-i]
        print(dp)
    print()

print(dp[k])