문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int arr[1002];
    int n;
    cin >> n;
    arr[1] = 1;
    arr[2] = 2;
    for(int i=3;i<=n;i++) {
        arr[i] = (arr[i-2] + arr[i-1]) % 10007;
    }
    cout << arr[n];
    return 0;
}

• 1X2 를 처음 두는 경우

  두 칸을 차지하므로, 2X(n-2)일 때의 경우의 이다. 즉, arr[n-2]

• 2X1 를 처음 두는 경우

  한 칸을 차지하므로, 2X(n-1)일 때의 경우이다. 즉, arr[n-1]

따라서 arr[k] = arr[k-2] + arr[k-1]