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

문제

백준 2294번 - 동전2

해결 과정

• 백준 2293번 - 동전1과 비슷한 문제
• 점화식: $dp[i] = min(dp[i], dp[i-coin]+1)$
  

풀이

import sys

n, k = map(int,sys.stdin.readline().split())

coin = []

coin = [int(sys.stdin.readline()) for _ in range(n)]

dp = [10001] * (k+1)
dp[0] = 0

for c in coin:
  for i in range(c,k+1):
    dp[i] = min(dp[i], dp[i-c]+1)

if dp[k] == 10001:
  print(-1)
else:
  print(dp[k])