problem-2293

ysysc·2022년 11월 19일
0

PS

목록 보기
26/47

과정
1. dp[i] = i를 만들 수 있는 경우의 수
2. for i in range(len(coin)) -> 각 코인에 대하여
3. for j in range(coin[i],k+1) -> 그 코인부터 k까지 (코인보다 작은 값은 만들지 못하기때문)
4. dp[j]+=dp[j-coin[i]] -> j (구하고자 하는 경우의 수의 코인) 에서 coin[i]만큼 뺀 값의 dp를 더함

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
coin=[int(input()) for i in range(n)]
dp=[0 for _ in range(k+1)]
dp[0]=1


for i in range(len(coin)):
    for j in range(coin[i],k+1):
        dp[j]+=dp[j-coin[i]]
print(dp[k])

time:80분
resolved:x

0개의 댓글