BOJ 11727 2xN 타일링 2

boj 11727 2xN 타일링 2

boj 11726 2xN 타일링 문제에서 2x2 타일이 추가된 경우이다. 똑같은 방식으로 테이블 D[i] = 1x2, 2x1, 2x2 타일로 채우는 경우의 수 라고 정의한다. 이 때, 다른 점은 끝에 2칸을 채우는 방법이 2x1 타일 2개를 이용하는 방법과 2x2 타일을 이용하는 방법으로 2가지이다. 그러므로 점화식으로D[i] = D[i-1] + 2xD[i-2] 를 설정하고 구현한다.

#include <iostream>
using namespace std;

int n;
int D[1005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    D[1] = 1;
    D[2] = 3;

    for (int i = 3; i <= n; i++)
    {
        D[i] = (D[i - 1] + 2 * D[i - 2]) % 10007;
    }

    cout << D[n];
}