[백준][Python] 2293번 동전1 - DP

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

2293번: 동전 1

 

 

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input().rstrip()) for _ in range(n)]

dp = [0]*(k+1)
dp[0] = 1

for coin in coins:
	for i in range(coin, k+1):
		dp[i] += dp[i-coin]
	print("동전", coin, "원일 때의 dp : ", dp)
print(dp[-1])