Pythonでインドの通貨単位を使ってnルピーを作る組み合わせの数を求めるプログラム

問題概要

額面が1ルピー・2ルピー・5ルピー・10ルピーのコインが、それぞれ限られた枚数だけ手元にあるとします。これらのコインを組み合わせて、合計がちょうどnルピーになる方法が何通りあるかを求めるのがこの問題です。サイズ4の配列countが与えられ、count[0]には1ルピーコインの枚数、count[1]には2ルピーコインの枚数、以降も同様に各額面の枚数が格納されています。

たとえば、入力が n = 25、count = [7, 3, 2, 2] の場合、答えは9通りになります。

解き方のアルゴリズム

この問題は動的計画法(DP)を応用して解けます。各額面のコインを1種類ずつ順に追加していき、その時点で各金額を作れる組み合わせの数を配列に記録していくのが基本的な考え方です。具体的な手順は以下のとおりです。

• denom := [1, 2, 5, 10] として、コインの額面を定義する
• A := サイズ(n + 1)の配列をすべて0で初期化する(各金額の作り方の数を管理)
• B := Aをコピーした新しいリストを用意する(次の額面を反映した結果の一時保管用)
• i を 0 から min(count[0], n) まで繰り返し、A[i] := 1 とする(1ルピーコインだけで作れる金額は必ず1通り)
• i を 1 から 3 まで繰り返し、残りの額面(2・5・10ルピー)を順に処理する:
  • j を 0 から count[i] まで繰り返し(その額面をj枚使うケース)、k を 0 から (n − j × denom[i]) まで繰り返して、B[k + j × denom[i]] := B[k + j × denom[i]] + A[k] と更新する
  • 処理が終わったら、j を 0 から n まで繰り返し、A[j] := B[j]、B[j] := 0 として結果をAに反映し、Bをリセットする
• 最後に A[n] を返す

Pythonでの実装例

それでは、実際のPythonコードを見てみましょう。

denom = [1, 2, 5, 10]

def solve(n, count):
   A = [0] * (n + 1)
   B = list(A)
   # 1ルピーコインだけで作れる金額を初期化
   for i in range(min(count[0], n) + 1):
      A[i] = 1
   # 残りの額面(2・5・10ルピー)を順に処理
   for i in range(1, 4):
      for j in range(0, count[i] + 1):
         for k in range(n + 1 - j * denom[i]):
            B[k + j * denom[i]] += A[k]
      # 結果をAに反映し、Bをリセット
      for j in range(0, n + 1):
         A[j] = B[j]
         B[j] = 0
   return A[n]

n = 25
count = [7, 3, 2, 2]
print(solve(n, count))

入力

n = 25, count = [7, 3, 2, 2]

出力

9

処理の流れのポイント

このアルゴリズムのポイントは、コインの種類ごとに段階を分けてDPテーブルを更新している点です。まず1ルピーコインだけで作れる金額(0〜min(count[0], n)ルピー)はそれぞれ1通りしかないため、A[i] = 1で初期化します。次に2ルピーコインについて、「0枚使う」「1枚使う」…「count[1]枚使う」というケースをすべて試し、既存の組み合わせ数に加算します。これを5ルピー、10ルピーについても順に繰り返すことで、同じ組み合わせを二重に数えることなく、すべてのパターンを正確に数え上げることができます。

計算量はおおよそ O(n × 使用コイン総数) となり、nやコインの枚数がそこまで大きくなければ十分高速に動作します。