C++で1×mサイズのタイルを使ってn×mの床を敷き詰める方法の数を数える

問題概要

部屋の床の長さと幅を表す 2 つの整数 n と m が与えられます。この床をサイズ 1×m のタイルで敷き詰める方法が何通りあるかを数えることが目的です。

入力例 1

n=3 m=2

出力例 1

1 x m サイズのタイルを使用して n x m の床を敷き詰める方法の数は:3

説明

下図のように、1×2 のタイル 3 枚を並べる方法が 3 通り存在します。

入力例 2

n=3 m=3

出力例 2

1 x m サイズのタイルを使用して n x m の床を敷き詰める方法の数は:2

説明

1×3 のタイル 3 枚をすべて縦方向に並べる方法と、すべて横方向に並べる方法があり、合計 2 通りとなります。

考え方(アプローチ)

このアプローチでは、n の値に応じて場合分けを行います。

• n が m より小さい場合(または n が 1 の場合):タイルの置き方は 1 通りのみです。
• n が m と等しい場合:すべて縦に並べる方法とすべて横に並べる方法の 2 通りがあります。
• n が m より大きい場合:それまでの計算結果を利用して、ways[n] = ways[n−1] + ways[n−m] として求めます。

アルゴリズムの手順

• 床とタイルの寸法として整数 n と m を受け取ります。
• 関数 ways_tile_floor(int N, int M) は寸法を受け取り、1×m サイズのタイルで n×m の床を敷き詰める方法の数を返します。
• 長さ N+1 の配列 arr[ ] を用意し、インデックス i(現在の N の値)における配置方法の数を格納します。
• arr[0] は 0 で初期化します。
• for ループで i=1 から i=N まで配列を走査します。各 arr[i] について、i > M の場合は前の値を使って arr[i] = arr[i − 1] + arr[i − M] と計算します。
• i = 1 または i < M の場合は、arr[i] を 1 に設定します。
• i = M の場合は、arr[i] = 2 とします。
• ループ終了後、arr[N] にタイルの配置方法の総数が格納されています。
• arr[N] を結果として返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int ways_tile_floor(int N, int M){
    int arr[N + 1];
    arr[0] = 0;
    for (int i = 1; i <= N; i++){
       if (i > M){
          arr[i] = arr[i − 1] + arr[i − M];
       }
       else if (i < M || i == 1){
          arr[i] = 1;
       } else {
          arr[i] = 2;
       }
   }
   return arr[N];
}
int main(){
   int n = 3, m = 2;
   cout<<"1 x m サイズのタイルを使用して n x m の床を敷き詰める方法の数:"<<ways_tile_floor(n, m);
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

1 x m サイズのタイルを使用して n x m の床を敷き詰める方法の数:3