[Python] 동전 1 - 백준 (DP)

해당 글은 백준 2293번 문제 '동전 1'을 다룬다.

문제

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

2293번: 동전 1

 

설명

해당 문제는 DP를 사용해서, 1부터 K원까지 돌며 각 동전으로 만들 수 있는 경우의 수를 더해주면 해결할 수 있다.

알고리즘 분류는 어떤건지 쉽게 떠오르는데, 그 알고리즘을 빠르게 구현하는게 어려운 것 같다..

 

코드

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

dp = [0]*(k+1)
dp[0]=1
for i in range(n):
    for j in range(coin[i], k+1):
        dp[j] = dp[j] + dp[j-coin[i]]
print(dp[k])