백준(2293) - 동전1 Python

백준(2293) - 동전1

문제풀이: DP, 파이썬

해결방법

dp 문제로 주어진 동전으로 만들 수 있는 경우의 수를 계속 더해나가면 된다.

dp[i] = dp[i] + dp[i-coin] 만 생각해내면 쉽게 해결할 수 있다.

예시)

3 10
1
2
5

import sys
input = sys.stdin.readline

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

print(dp[k])