[백준] 2294 동전2 - python

문제 링크
https://www.acmicpc.net/problem/2294

이것이 코딩 테스트다 with 파이썬 책에 실린 효율적인 화폐 구성 과 같은 유형의 문제이다.

시도1. 성공

n, k = map(int, input().split())

coins = []
dp = [100000] * 10001
dp[0] = 0
for _ in range(n):
  coins.append(int(input()))
  
for i in range(n):
  for j in range(coins[i], k+1):
      dp[j] = min(dp[j - coins[i]]+1, dp[j])

print(dp[k] if dp[k] != 100000 else -1)

• 접근방법 : 다이나믹 프로그래밍