[백준] 동전 1

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

2293번: 동전 1

 

dp[k] = k원을 만들 수 있는 경우의 수

n번 돌 때마다 dp 배열은 갱신된다. (n번째는 n개의 수를 가지고 k원을 만들 수 있는 경우의 수) 

 

import sys

n, k = map(int, sys.stdin.readline().split())
dp = [0] * (k+1)
dp[0] = 1

for i in range(1, n+1):
    m = int(sys.stdin.readline())
    
    for j in range(k+1):
        if j - m >= 0:   
            dp[j] += dp[j-m]
        
print(dp[-1])