[BOJ] 동전 1

---

코드

from sys import stdin
input = stdin.readline

# input
n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))

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

print(dp[k])

결과

풀이 방법

• 다이나믹 프로그래밍 문제라고 생각했으나 점화식을 세우기가 어려웠다.
• 동전 종류를 순회하면서, 해당 동전 금액(c)을 더하여 총합 i의 금액을 채울 수 있다면 dp[i]에 dp[i-c]를 합산하는 것이 핵심이다.

---