[백준] 동전1

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

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

풀이

DP 문제로 풀어야한다. 가치의 합이 k원이 되는 경우의 수를 구하기 위해, 가치의 합이 i (0<=i<=k)원이 되는 경우의 수를 구하는 것부터 해야한다.

동전 1을 통해 1~10 원을 만드는 경우는 모두 1이다.

동전 2가 추가되었을 때, 1원은 만들기 어렵다. 2원을 만드는 경우의 수는 1로 만드는 경우 [1,1]와 함께 [2]로 갱신된다. 3원을 만드는 경우의 수는 [1,1,1], [1,2]로 갱신된다. 여기에서 [1,2]는 1원을 만드는 경우의 수 [1] 에 2를 추가하는 것이다.
마찬가지로 4원을 만드는 경우도 [1,1,1,1]와 함께 [1,2,2], [2,2]로 갱신된다.

따라서 점화식으로 dp[i] = dp[i] + dp[i-coin]이 된다.

파이썬 코드로 아래와 같이 풀 수 있다.

코드

n,k = map(int, input().split())

coins = []
for i in range(n):
    coins.append(int(input()))

dp = [0 for i in range(k+1)]
dp[0] = 1

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

print(dp[k])