BOJ 2293: 동전 1 [Python 3]

평범한 dynamic programming 문제이다.

n,k=map(int,input().split())
coindata=[]
for _ in range(n):
    coindata.append(int(input()))
coindata.sort()
values=[0 for _ in range(k+1)]
values[0]=1
for i in coindata:
    for j in range(1,k+1):
        if j-i>=0:
            values[j]+=values[j-i]
print(values[k])

0원부터 k원까지 개수를 셀 수 있는 리스트를 만들고, 

거기에 1월부터 k원까지 가능한 개수를 모두 센다.

반복문에서,

현재 돈의 크기에 (현재 돈 - 동전의 크기)일 때의 개수를 더해준다.