취준/백준
[백준][Python][2293][DP] 동전 1
puff
2020. 2. 28. 12:41
문제 : https://www.acmicpc.net/problem/2293
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
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])