2 xnタイル

タイムアウトメモリ制限回答者正解率1秒256 MB 10506539690290835.517%

質問する

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

入力

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

しゅつりょく

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

入力例1

2

サンプル出力1

2

入力例2

9

サンプル出力2

55

コード#コード#

import java.io.*;

public class P_11726 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] rectangle = new int[1001];

        rectangle[1] = 1;
        rectangle[2] = 2;
        for (int i = 3; i <= n; i++) rectangle[i] = (rectangle[i - 1] + rectangle[i - 2]) % 10007;

        bw.write(Integer.toString(rectangle[n]));
        bw.flush();
    }
}

コードの説明

dp[n]は2 xnタイルの矩形を充填する最大の方法数である.
問題で与えられたタイルの破片は1 x 2と2 x 1しかない.
ではdp[n]は、dp[n−1]のフラグメントに2 x 1のフラグメントを追加する方法数、d[n−2]のフラグメントに1 x 2のフラグメントを2つ追加する方法数といえる.