[シルバー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)
Reference
この問題について([シルバー1]2294号:コイン2), 我々は、より多くの情報をここで見つけました https://velog.io/@hyunnn/실버1-2294번-동전2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol