동전 사용 개수의 최솟값 저장을 위해 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)