[シルバー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)