[白俊]10162号-(Python)-Greedy

935 ワード
greedy 白駿 テキストリンク
質問リンク:https://www.acmicpc.net/problem/10162

この問題はグリディアルゴリズムで解決した.
欲張りアルゴリズムは欲張りアルゴリズムとも呼ばれ、様々なタイプを解くとなぜ欲張りなのかがわかります.これは結果を考慮せずに、各段階で最適な選択をする方法です.したがって,DP(ダイナミックプランニング法)とは逆(?)強烈な感じ.グリディは100%のベストを保証できないが、問題のタイプによっては速い場合が多い.2つの問題のタイプにはそれぞれメリットとデメリットがあり、問題を読んだ後、どのアルゴリズムがもっと適切かを自分で判断すればもっと速くなる.
グリディアルゴリズムの代表的なタイプである「お金を探す」問題とよく似ている.
入力時間が10を超えない場合は、-1を出力します.
分かれば300、60、10に分かれます.分けるときは分を順番に貯めて、最後に順番に出力すればいいです.
n = int(input())

a = [300, 60, 10]
b = []
if n % 10 != 0:
  print(-1)
else:
  for i in a:
    if n >= i:
      b.append(n // i)
      n = n % i
    else:
      b.append(0)
  for i in b:
    print(i, end=' ')
[Leet Code] Evaluate Reverse Polish Notation
白駿11505区間乗