【C++】隣り合う2段が同時に黄色にならないように階段を2色で塗る方法の総数を求める

n個の階段と、それらを塗るための2色（赤・黄）が与えられます。この記事では、「隣り合う2段がどちらも黄色にならない」という条件を満たしながら階段を塗る方法が何通りあるのかを数える問題を、C++で解いていきます。

まずは具体例で問題の内容を確認してみましょう。

入力例

3

出力例

5

説明

条件を満たす塗り方は「YRY」「RYR」「YRR」「RRY」「RRR」の5通りです。ここで R は赤色、Y は黄色を表します。

規則性を見つける

この問題を解くために、段数が増えたときの塗り方の数を順番に観察してみましょう。

• N = 1 のとき、ways(1) = 2：R、Y
• N = 2 のとき、ways(2) = 3：RY、YR、RR
• N = 3 のとき、ways(3) = 5：RYR、YRY、RRY、YRR、RRR
• N = 4 のとき、ways(4) = 8：YRYR、RYRY、RYRR、YRRY、YRRR、RRYR、RRRR、RRRY

これらの結果から、塗り方の総数は「初項が2、第2項が3」のフィボナッチ数列として求められることが分かります。

なぜフィボナッチ数列になるのか

理由はシンプルです。n段目を赤で塗る場合、直前の段が何色でも制約に違反しないため、そこまでの(n-1)段の塗り方は ways(n-1) 通りあります。一方、n段目を黄で塗る場合は、(n-1)段目が必ず赤でなければならないため、その組み合わせは ways(n-2) 通りになります。よって次の漸化式が成り立ちます。

ways(n) = ways(n-1) + ways(n-2)

C++での実装例

このロジックをそのままプログラムにすると、以下のようになります。

#include <iostream>
using namespace std;
int colorSteps(int n) {
    int first = 2;
    int next = 3;
    for (int i = 3; i <= n; i++) {
        next = first + next;
        first = next - first;
    }
    return next;
}
int main(){
    int n = 6;
    cout<<"Number of ways to color "<<n<<" steps is "<<colorSteps(n);
    return 0;
}

実行結果

Number of ways to color 6 steps is 21

このプログラムはループで一度ずつ計算を進めていくだけなので、時間計算量は O(n)、追加のメモリも定数 O(1) で済む、非常に効率的な解法となっています。