백준(BOJ) 11727번 2xn 타일링 2

문제 :  https://www.acmicpc.net/problem/11727

입력

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

출력

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

나의 풀이:

2xn 타일링 문제 ( https://100100e.tistory.com/24 ) 와 거의 동일했다. 다른 점은 2x2 타일이 추가 된 것인데

마찬가지로 타일을 어떻게 덮었는지는 상관이 없다. 따라서 n-2를 채우는 방법이 2x2 타일을 쓰는 것과 2*1타일 두개를 가로로 배치한

두가지 방법이 될 것 . 따라서 tiling(n-2) 에 2배를 곱해주면 된다.

코드 ( C + + )

#include <iostream>

#include <cstring>

using namespace std;

int N;

const int MAX = 1000;

int cache[MAX+1];

int tiling(int n)

{

if (n <= 1) return 1;

int& ret = cache[n];

if (ret != -1)

return ret;

return ret = (tiling(n - 1) + (2*tiling(n - 2)))%10007;

}

int main()

{

cin >> N;

memset(cache, -1, sizeof(cache));

int result = tiling(N);

cout << result << endl;

return 0;

}