[BOJ 11726]2 xnタイル

質問する

2×nサイズ1の矩形×2, 2×タイルで充填する方法の数を求めるプログラムを作成してください.
下図2×5長方形を充填する方法の一例.

入力

最初の行はnです.(1 ≤ n ≤ 1,000)

しゅつりょく

1行目2×n矩形を充填する方法数を10007で割った後、残りを出力する.

コピー例入力1

2

コピー例出力1

2

コピー例入力2

9

コピーサンプル出力2

55

問題を解く心得

DPの点火式の問題を探します!f(1)からf(5)まで描くと、ルールが見つかります.

N=4の場合は例を挙げましょう!
全部で5つの状況があり,2つの状況に分かれている.
N=3の場合のタイル+1個縦
N=2の場合のタイル+2 x 2は2つあります
N=5の場合も同様の方法で状況の数を求め、点火式を確立することができる.
F(n) = F(n-1) + F(n-2)

マイコード

N = int(input())
if N == 1:
    print(1)
else:
    dp = [0 for _ in range(N + 1)]
    dp[1], dp[2] = 1, 2

    for i in range(3, N + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    print(dp[-1] % 10007)