FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の動的計画法で、合計5を作る組合せ数を求める。戻り値はどれ…
問題
次の動的計画法で、合計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
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は順序違いを別物として数えたときに出やすい値です。外側を硬貨、内側を金額にする意味を押さえておきましょう。
このコードの正体：これは「硬貨を何枚でも使える組合せ数え上げ」、いわゆる無制限ナップサックのDPです。内側ループでsをcから昇順に増やしdp[s]にdp[s-c]を足すため、同じ硬貨を繰り返し使え、外側を硬貨にすることで{1,2,2}と{2,2,1}を同一視できます。計算量は硬貨数×金額に比例します。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。