[Python] 백준 2293 - 동전 1

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

2293번: 동전 1

 

최근에 DP를 배우고 DP문제에 재미들렸다. DP가 유독 생각하는 시간이 코드 수정하는 시간보다 많은 알고리즘인 것 같다. DP 코드가 대체적으로 길지 않은데 어렵다보니 매력적인 알고리즘이다.

이 동전 문제도 DP문제 중 대표적인 유형이라고 볼 수 있을 것 같다. 이전에 공부했던 내용이라 금방 풀었음.

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 j in range(coin, k+1):
        dp[j] = dp[j] + dp[j-coin]

print(dp[k])