[BOJ 2293] 동전 1(Python)

문제

동전 1

---

문제 해설

DP는 아무리 쉬운 문제라도 문제를 부분 문제로 나눈뒤 점화식을 구하는 과정이 가장 어려운 것 같습니다.

점화식은 다음과 같습니다.

dp[n] = dp[n] + dp[n-k] (단, n-k >= 0)
(n = 이전 동전으로 만들수 있는 경우의 수)
(k = 현재 동전의 가치)

---

풀이 코드

import sys

input = sys.stdin.readline
n, k = map(int, input().rstrip().split())
coins = []
dp = [0] * (k + 1)
dp[0] = 1

for _ in range(n):
    coin = int(input())
    coins.append(coin)

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

---