[BOJ]2294コイン2

4233 ワード
テキストリンク
📃 銅貨

に答える


各値には、必要な最小コイン数を格納するためにDP配列が必要です.
  • データを1次元配列に格納します.
  • の最小硬貨数を保存するdp配列を作成し、max(10001)に初期化します.
  • 硬貨アレイの値と
    • を取得します.
  • の価格でfor文を返します.
  • 現在値から導入した硬貨値を減算した硬貨使用個数は、現在1個の硬貨のみを加算した値と、以前1個の硬貨のみを加算した場合に用いた硬貨数と比較して、より小さい値をdp配列に含む.

    • コード#コード#

    import sys
input = sys.stdin.readline
n, k = map(int, input().split())

li =[]

for i in range(n):
   li.append(int(input()))

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

for num in li:
   for i in range(num, k+1):
       dp[i] = min(dp[i],dp[i-num]+1)
if dp[k] == 10001:
   print(-1)
else:
   print(dp[k])
    「文字列を整数に変換」問題のJavaScriptアルゴリズム
    WebアプリケーションPostMessageイベントが無効です