基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
動的計画法の状態
条件を整理し、答えを選んでから解き方を確認しましょう。
硬貨1円・3円・4円を何枚でも使う。D[x]をx円を作る最少枚数、D[0]=0とする。D[6]はどれか。
答え・解き方を読む
2枚
考える順序
- 13円を2枚使うと6円
- 21枚では6円の硬貨がない
- 3従って最少2枚で、大きい4円から選ぶ方法より少ない
選択肢ごとの理由
- 比較 · 6枚
1円だけを使う解は最適ではありません。
- 正解 · 2枚
3円を2枚使うと6円。1枚では6円の硬貨がない。従って最少2枚で、大きい4円から選ぶ方法より少ない。
- 比較 · 3枚
4+1+1は可能ですが最少ではありません。
- 比較 · 4枚
より少ない3+3という組合せがあります。