[백준/2294][Python] 동전2

문제

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

2294번: 동전 2

풀이

DP문제이다. 

i번째 coins를 쓰는 경우, 안쓰는 경우를 비교한다.
i번째 coins을 쓰면 dp[j-coins[i]] + 1이 점화식이다. 5원을 써서 11원 만드는 방법을 고안한다 하면, dp[11]과 dp[11-5] + 1을 비교한다. 

어렵다.......................... dp어케하냐

코드

n,k = map(int,input().split())
coins = []
for i in range(n):
    coins.append(int(input()))
coins = sorted(coins)
dp = [10001] * (k+1)
dp[0]=0
for i in range(n):
    for j in range(coins[i],k+1):
        dp[j] = min(dp[j-coins[i]]+1, dp[j])
if dp[-1]==10001:
    print(-1)
else:
    print(dp[-1])