[백준-2293] 동전 1

나의 코드

import sys
input = sys.stdin.readline

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

for _ in range(n):  
    c=int(input())
    if c<=k:
        dp[c]+=1
    for i in range(c+1,k+1):
        dp[i]+=dp[i-c]
print(dp[k])

수행시간: 263ms

풀이

dp[i]에는 동전 가치의 합이 i인 경우의 수이다.
입력받은 수를 c라고 할 때 i는 i-c의 경우들에 c를 그냥 더하면 되므로 dp[i]+=dp[i-c]가 된다.

만약 동전의 가치가 1,2,5 이면 dp[10]=dp[9]+dp[8]+dp[5] 인데 문제에 구성은 같고 순서만 다른거는 같은 경우로 본다했기때문에 이렇게 한번에 처리하면 안되고
한개씩 처리를 해줘야한다.