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

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

2293번: 동전 1

DP 문제다.

 

어떠한 동전 c 를 이용해서 1-x를 만드는 모든 방법을 value에 더하는 방식으로 구할 수 있다.

 

첫번째 동전까지 이용해서 x를 만드는 경우의 수 +

두번째                            ''                                +

세번째                            ''                                +

...

...

를 하면 모든 동전을 사용하여 x 를 만드는 모든 경우의 수를 구할 수 있다.

이때, 동전값을 c라 할 때, x-c >=0, 즉 목표값보다 동전값이 작을 때만 이전의 경우의 수 value[x-c]를 더할 수 있다.

 

 

import sys

n, k = [int(i) for i in sys.stdin.readline().split()]
coins = []
for _ in range(n):
    coins.append(int(sys.stdin.readline()))

value = [0]*(k+1)

value[0] = 1
for c in coins:
    for x in range(1, k+1):
        if x-c >= 0:
            value[x] += value[x-c]

print(value[-1])