スパルタン3655週(5)硬貨2

注意:黄牛開発者

第5週

白駿2294号硬貨2

質問リンク:https://www.acmicpc.net/problem/2294

💡 悩む

点火式

の作成方法

硬貨の個数は最低にしなければならないので、minを使いますよね?

いつの数と比較しますか?

硬貨の配列と結びつける方法

解決策

可能な方法をすべて列挙して使用します.

ex.12元であれば、コイン配列のコインを外す場合は本人と比較します
dp[12-5]+1 , dp[12]

!! スキル

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

悟る

出力部において

の異常処理、

を実行するようにしてもよい.

は、点火式

の確立の練習を継続する.

に答える

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [0] * n
dp = [10001] * (k+1)
dp[0] = 0
for i in range(n):
    coins[i] = int(input())

coins.sort()
for coin in coins:
    for i in range(coin, k+1):
        dp[i] = min(dp[i-coin]+1, dp[i])

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