科目Bの貪欲法問題の解き方｜おつりの枚数を大きい順に追う

おつりを大きい硬貨から数えるのは分かる。でも、コードになると商と余りのどちらを見ているのか分からなくなる。

科目Bの問題で、硬貨の配列と割り算が並んだコードを見て、手が止まったことはありませんか？

貪欲法という言葉を聞くと、何か特別なアルゴリズムのように感じるかもしれません。名前の印象が強くて、身構えてしまう人も多いのではないでしょうか。

大丈夫です。科目Bで出る貪欲法は、そのときいちばん大きいものから順に選んでいく、という手順のくり返しです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、在庫を大きい梱包単位から順に割り当てる処理を書いたことがあり、並び順を一つ間違えただけで出荷数が合わなくなった経験があります。

そのとき原因を見つけられたのは、小さな数で1行ずつ値を書き出したからでした。貪欲法の問題も、同じやり方で落ち着いて追えます。

この記事では、貪欲法の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

貪欲法の問題は何を聞いているのか¶

最初に、貪欲法とは何かを短く押さえておきましょう。名前は少し大げさですが、やっていることはとても素直です。

貪欲法とは、先のことは考えずに、いまの時点でいちばんよさそうなものを選び続ける方法のことです。一度選んだものは取り消さず、そのまま次の選択に進みます。

身近な例は、お店のレジでおつりを渡す場面です。780円のおつりを渡すとき、店員さんはまず500円玉を1枚取り、次に100円玉を2枚取ります。

残りが80円になったら50円玉を1枚、最後に10円玉を3枚です。大きい硬貨から順に、入るだけ入れていくこの手順が、貪欲法の基本形になります。

科目Bで問われる形¶

試験の擬似言語で貪欲法が出るときは、考え方そのものより、硬貨の並びや計算の行が問われます。どんな形で聞かれやすいのかを、表に整理しました。

どの形でも、中心にあるのは、何枚使えるかを出す商の行と、残りを出す余りの行です。この2行を小さな例で確かめられれば、問われ方が変わっても同じ手順で解けます。

動的計画法の問題との違い¶

貪欲法とよく比べられるのが、動的計画法です。どちらも最少の枚数や最大の値を求める問題に使われますが、考え方は正反対といってよいほど違います。

貪欲法は、いまの一手だけを見て決め、あとから見直しません。動的計画法は、小さい金額すべての答えを表にためてから、全体の答えを決めます。

表を埋めて答えを出す側の追い方は、こちらの記事で詳しく扱っています。

【関連記事】科目Bの動的計画法の問題の解き方｜表を小さい順に埋めて追う

まず目を付ける場所¶

貪欲法が何かつかめたら、次はコードのどこから読むかを決めます。おつりの問題では、目を付ける場所が3つあります。

ひとつ目は硬貨の配列の並び順、ふたつ目は商を使う行、みっつ目は余りを使う行です。この3か所が分かれば、ずれた選択肢をほぼ見抜けます。

硬貨の配列は大きい順に並んでいるか¶

最初に確かめたいのが、硬貨の配列がどの順に並んでいるかです。貪欲法は大きいものから選ぶ方法なので、配列も大きい順に並んでいなければなりません。

もし小さい順に並んでいたら、どうなるでしょうか？ 最初に1円玉で全額を払ってしまい、500円玉の出番が来なくなります。

並び順が逆のまま渡される問題では、配列を後ろから読むループになっているはずです。ループの開始位置と、増やすのか減らすのかを一緒に確認しましょう。

商の行は何枚使えるかを出している¶

次に見るのが、残りの金額を硬貨の額で割った商を求めている行です。780円を500円で割った商は1なので、500円玉は1枚使えると分かります。

商とは、割り算で何回分入るかを表す数です。割り算の商と余りの考え方そのものに不安がある場合は、こちらの記事で先に整理しておくと読みやすくなります。

【関連記事】擬似言語の余り（剰余）と割り算がわからない人へ｜偶数判定と桁の取り出しを解説

余りの行は次に払う金額を出している¶

最後に見るのが、残りの金額を余りで置き換えている行です。780円を500円で割った余りは280円で、これが次の硬貨で払う金額になります。

この行が抜けていると、次の硬貨でもまた780円から数え始めてしまいます。商で枚数を数え、余りで残りを減らす、という2行で1組だと覚えておきましょう。

例題：おつりの硬貨の枚数を数える¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、おつりの金額を受け取り、使う硬貨の枚数の合計を返す関数です。配列の添字は1から始まります。

○整数型: countCoins(整数型: amount)
  整数型の配列: coins ← {500, 100, 50, 10, 5, 1}
  整数型: rest ← amount
  整数型: total ← 0
  整数型: i, n
  for (i を 1 から coinsの要素数 まで 1 ずつ増やす)
    n ← rest ÷ coins[i] の商
    total ← total ＋ n
    rest ← rest mod coins[i]
  endfor
  return total

countCoins は、まず残りの金額 rest におつり全体を入れます。そのあと、大きい硬貨から順に、何枚使えるかを商で求めて total に足し、残りを余りで置き換えていきます。

では、countCoins(780) の戻り値は何になるでしょうか？

トレース表で残りの金額を追う¶

頭の中だけで割り算を続けると、いま何円残っているのかが分からなくなりがちです。そこで、ループ1回ごとに、硬貨の額、商、合計枚数、残りの金額をトレース表に書きます。

ポイントは、残りの金額の列を最後に置き、次の行の計算がその値から始まることを確かめながら進めることです。こうしておくと、金額が少しずつ減っていく様子が一目で分かります。

4回目の時点で rest が 0 になり、そのあとの商はすべて 0 です。return total で 7 を返すので、戻り値は 7 になります。

残りが 0 になってもループは最後まで回る、という点に注意してください。途中の値を聞く設問では、5回目や6回目も表に書いておくと数え間違いを防げます。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

割り算を使わずに引き算で書く形¶

同じ処理は、割り算を使わずに書かれることもあります。残りの金額が硬貨の額以上である間、1枚ずつ引いて数える形です。

  for (i を 1 から coinsの要素数 まで 1 ずつ増やす)
    while (rest ≧ coins[i])
      rest ← rest − coins[i]
      total ← total ＋ 1
    endwhile
  endfor

この形では、while の中で1枚ずつ数えるので、トレース表の行が増えます。けれども、結果は商と余りを使う形とまったく同じです。

試験では、どちらの書き方が出ても慌てる必要はありません。while の条件が成り立つ回数が商、抜けたときの rest が余りだと読み替えれば、同じ表で追えます。

硬貨の枚数を記録する形¶

設問によっては、合計枚数ではなく、硬貨ごとの枚数を配列に残すこともあります。その場合は total ← total ＋ n の代わりに、cnt[i] ← n のような行が入ります。

780円なら、cnt は {1, 2, 1, 3, 0, 0} になります。添字が硬貨の配列と対応していることを確かめれば、どの硬貨が何枚かをそのまま読み取れます。

間違いやすい選択肢の見分け方¶

貪欲法の問題では、並び順や計算の行を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の countCoins(780) を使って、よくある誤りを表にまとめました。

正解の 7 に対して、0 や 780 のように極端な数字が並ぶこともあれば、途中の値が紛れ込むこともあります。計算結果だけを見て選ぶと、思わぬ選択肢に飛びついてしまいます。

小さい金額で選択肢を試す¶

式で迷ったら、金額を 60 や 15 のような小さい値にしてみてください。60円なら、50円玉1枚と10円玉1枚の2枚だと、手で数えればすぐに分かります。

正しいコードなら total は 2 になり、手で数えた数と一致します。残りを更新しないコードだと、50円で1枚、10円で6枚、5円で12枚と数えてしまい、2 よりずっと大きくなるので、すぐに誤りだと分かります。

小さい入力は、答えを手で確かめられる、いちばん信頼できる道具です。選択肢ごとに1回試すだけで、ずれたコードをほとんど落とせます。

貪欲法で最少にならない硬貨の組合せ¶

もう一つ押さえておきたいのが、貪欲法がいつでも最少の枚数を出すわけではない、という点です。日本の硬貨では大きい順に選べば最少になりますが、硬貨の額が変わると話が違ってきます。

たとえば、硬貨が 4円、3円、1円の3種類しかない国で、6円を払う場合を考えてみましょう。比べやすいように、2つの選び方を表に並べます。

貪欲法は最初に4円を選んだ時点で、あとから3円2枚に切り替えることができません。いまの一手だけで決めて見直さない、という性質がそのまま裏目に出た例です。

このような組合せで最少を確実に求めたいときは、小さい金額から順に答えを表にためる動的計画法を使います。設問に、最少になることを示せ、や、正しくない場合はどれか、という言葉があったら、この違いが問われていると考えましょう。

並べ替えの手順そのものを追う練習をしておくと、配列の並び順を確かめる目も育ちます。あわせて読んでおくと、大きい順に並んでいるかを見る感覚がつかみやすくなります。

【関連記事】科目Bのソート問題を解くコツ｜交換される値を追ってみよう

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。割り算と余りが交互に出てくる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの回で予想とずれたのかがすぐに分かります。

試すときは、まず正しい countCoins を動かして、780円で total が 7 になるのを確かめてください。そのあと、rest を更新する行を消してみて、total が一気に大きくなる様子を見ると、余りの行の役割が体で分かります。

慣れてきたら、硬貨の配列を {4, 3, 1} に変えて 6 を渡してみましょう。手で数えた最少の2枚と、貪欲法が返す3枚の違いを自分の目で確かめられます。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、残りの金額が1行ごとに減っていく様子を確かめてみてください。

まとめ¶

科目Bの貪欲法の問題は、難しい理論を問うものではありません。大きい順に並んだ硬貨を、商で数えて余りで減らす、という2行の組を追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、100円未満の小さな金額で十分です。何度か表を書くうちに、商と余りの2行を見ただけで、何枚使って何円残るのかが分かるようになります。

商で枚数を数え、余りで残りを減らす。答えに迷ったら小さい金額を手で数える。 この2つを習慣にしておけば、貪欲法の問題にも自信を持って向き合えます。次に硬貨の配列が出てきたら、まずは並び順を確かめるところから始めてみてください。