[파이썬] [DP] 백준 2293 동전 1

문제

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

2293번: 동전 1

코드

import sys
input=sys.stdin.readline

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

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

dp[0]=1

for i in c:
    for j in range(1,k+1):
        if j-i>=0:
            dp[j]+=dp[j-i]

print(dp[k])

생각 정리

	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
i = 1	개수(1)	1 개수(1)	1 + 1 개수(1)	1 + 1 + 1 개수(1)	1 + 1 + 1 + 1 개수(1)	1 + 1 + 1 + 1 + 1 개수(1)	1 + 1 + 1 + 1 + 1 + 1 개수(1)
i = 2			2 개수(1)	1 + 2 개수(1)	1 + 1 + 2 2 + 2 개수(2)	1 + 1 + 1 + 2 1 + 2 + 2 개수(2)	1 + 1 + 1 + 1 + 2 1 + 1 + 2 + 2 2 + 2 + 2 개수(3)
i = 5						5 개수(1)	5 + 1 개수(1)