[BOJ] 2293. 동전1 (🥇, DP)

🔗

풀이

1원으로 10원을 만드는 방법에 대해 생각해보자. 처음엔 1원이 있을 것이다. 1원으로 1원을 만드는 방법은 한 가지다. 그렇다면 1원으로 2원을 만드는 방법은? 1원에다가 1원을 더하는 방법 한 가지다. 그렇다면 1원으로 3원을 만드는 방법은 몇 가지일까. 마찬가지로 2원을 만드는 방법에 1원을 더하는 방법 한 가지다. n원으로 k원으로 만드는 방법은 n원으로 k-1원을 만드는 방법과 같은 셈이다.

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 작은 문제의 해결법으로 큰 문제를 해결할 수 있는 알고리즘 풀이 방식이다. 10원을 만들 수 있는 가짓수는 그보다 작은 k원을 만드는 방법들의 가짓수를 통해서 구할 수 있다.

점화식은 다음과 같다. 동전 n는 여러가지이므로 누적으로 더해나가야 한다.

dp[k] += dp[k-n]

# 동전 1

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [0]*(k+1)

for i in range(n):
    coin = coins[i]
    if coin > k:
        continue
    dp[coin] += 1
    for j in range(coin+1, k+1):
        dp[j] += dp[j-coin]

print(dp[k])