Pythonで水平方向のレンガ敷き詰めパターンの総数を求めるプログラム

問題の概要

数値のリスト bricks と、2つの値 width(幅)および height(高さ)が与えられているとします。リストの各要素 bricks[i] は、長さが bricks[i] 単位、幅が1単位のレンガを表します。このとき、指定された幅と高さの領域をレンガで完全に敷き詰める方法が何通りあるかを求める必要があります。

なお、レンガは何度でも再利用できますが、水平方向にのみ配置できるという制約があります。

入力例

たとえば、入力が bricks = [2, 1]、width = 3、height = 2 の場合、出力は 9 になります。これは、幅3・高さ2の領域を長さ1と長さ2のレンガで敷き詰める組み合わせが、各行に3通り存在し、それが2行分で合計 3 × 3 = 9 通りになるためです。

解決のアプローチ

この問題は、動的計画法(DP)を使って効率的に解くことができます。基本的な考え方は次のとおりです。

• まず、幅ごとの「その位置まで敷き詰める方法の数」を記録する配列 w を用意します。サイズは width + 1 とし、先頭(位置0)には1を、それ以外には0を設定します。
• 各位置 i を左から順に走査します。w[i] が0でない場合(つまりその位置に到達する方法が存在する場合)、使用可能なすべてのレンガの長さ x について、i + x が幅以内に収まるならば、w[i + x] に w[i] を加算します。
• 最終的に w[width] には「1行分を完全に敷き詰める方法の総数」が格納されます。
• 各行は独立して敷き詰められるため、全体の答えは w[width] の height 乗となります。

実装例(Python)

以下に、上記のアルゴリズムを実装したPythonコードを示します。

def solve(bricks, width, height):
    # 幅ごとの敷き詰め方の数を記録する配列(位置0のみ1で初期化)
    w = [1] + [0] * width
    for i in range(width):
        if w[i]:
            for x in bricks:
                if i + x <= width:
                    w[i + x] += w[i]
    # 1行分の組合せ数を高さ分だけ累乗する
    return w[width] ** height

bricks = [2, 1]
width = 3
height = 2
print(solve(bricks, width, height))

入力

[2, 1], 3, 2

出力

9

計算量について

このアルゴリズムの時間計算量は O(width × len(bricks)) であり、幅やレンガの種類が増えても現実的な時間で処理できます。また、最終的な累乗計算はPythonの組み込み演算子 ** によって高速に行われるため、高さが大きい場合にも対応可能です。