[실버1] 2294번 : 동전2

🛠 문제

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

👩🏻‍💻 해결 방법

동전 사용 개수의 최솟값 저장을 위해 dp를 100001로 초기화해주었다
동전 단위를 하나씩 사용하면서 최솟값을 갱신해주는 점화식을 세웠다

소스 코드

import sys 
input = sys.stdin.readline

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

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

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

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