PythonでNが{A, B}の繰り返し足し算で表現できるかどうかを判定する方法

ある数値 target と、2つの整数 A と B が与えられたとき、A と B をそれぞれ何度でも足し合わせることで target を作り出せるかどうかを判定する問題を考えてみましょう。

例えば、Target = 26、A = 5、B = 7 という入力の場合、出力は True になります。これは (7 + 7 + 7 + 5) のように A と B を組み合わせることで 26 を作れるためです。

解法のアプローチ

この問題は、深さ優先探索（DFS）とメモ化を組み合わせることで効率的に解けます。基本的な考え方は、「0 から出発して A または B を足し続け、target に到達できる経路が存在するか」を探索するというものです。

具体的な手順は以下の通りです。

• util() 関数を定義します。引数は x、a、b、is_ok、target です。
• x > target の場合は、これ以上探索しても意味がないため return します。
• is_ok[x] が既に True の場合も return します（同じ値の再探索を防ぐメモ化）。
• is_ok[x] := True と設定し、到達可能な合計値として記録します。
• util(x + a, a, b, is_ok, target) と util(x + b, a, b, is_ok, target) を再帰的に呼び出します。

メインの処理では次のようにします。

• サイズ (target + 1) の配列 is_ok を False で初期化して用意します。
• util(0, a, b, is_ok, target) を呼び出して探索を開始します。
• 最後に is_ok[target] を返します。True なら target は作成可能です。

実装例

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

def util(x, a, b, is_ok, target):
    if x > target:
        return
    if is_ok[x]:
        return
    is_ok[x] = True
    util(x + a, a, b, is_ok, target)
    util(x + b, a, b, is_ok, target)

def solve(target, a, b):
    is_ok = [False] * (target + 1)
    util(0, a, b, is_ok, target)
    return is_ok[target]

target = 26
A = 5
B = 7
print(solve(target, A, B))

入力

26, 5, 7

出力

True

計算量について

このアルゴリズムでは、各合計値（0 から target まで）は一度しか訪問されないため、時間計算量は O(target)、空間計算量も O(target) となります。メモ化によって無駄な再帰呼び出しが排除されるため、大きな target に対しても効率的に動作します。