FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の動的計画法で，合計5を作る組合せ数を求める。戻り値はどれか。
整数型の配列: coin ← {1, 2, 5}
整数型の配列: dp[0..5] ← {1, 0, 0, 0, 0, 0}
整数型: c, s
for (coinの各要素 c を先頭から順に取り出す)
for (s を c から 5 まで 1ずつ増やす)
dp[s] ← dp[s] ＋ dp[s - c]
endfor
endfor
return dp[5]- ア 3
- イ 4
- ウ 5
- エ 6
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
正解：4
dp[s]は，処理済みの硬貨だけを使って合計sを作る組合せ数である。coin=1の後は全て1通り，coin=2を加えると2を使う組合せが増え，最後にcoin=5を加えるとdp[5]にdp[0]が足される。
| 処理した硬貨 | dp[0..5] |
|---|---|
| 1 | {1,1,1,1,1,1} |
| 2 | {1,1,2,2,3,3} |
| 5 | {1,1,2,2,3,4} |
return dp[5]は4。順列ではなく組合せなので，硬貨の外側ループの順序が重要である。
選択肢の見分け方：3は硬貨5を使う組合せを足し忘れた値，5や6は順序違いを別物として数えたときに出やすい。外側を硬貨，内側を金額にする意味を押さえる。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。