// 2×n 직사각형을 1×2, 2×1 타일로 채우는 방법의 수
// 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
int tile1(int n) {
int a = 1;
int b = 2;
if (n == 1) {
return a;
} else if (n == 2) {
return b;
}
int result = 0;
for (int i = 2; i < n; i++) {
result = a + b;
a = b;
b = result;
}
return result % 10007;
}
// 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수
// 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
int tile2(int n) {
int a = 1;
int b = 3;
if (n == 1) {
return a;
} else if (n == 2) {
return b;
}
int result = 0;
for (int i = 2; i < n; i++) {
result = a*2 + b;
a = b;
b = result;
}
return result % 10007;
}
//3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수
int tile3(int n) {
if(n == 0) return 1;
if(n == 1) return 0;
if(n == 2) return 3;
if (arr[n] != 0) {
return arr[n];
}
arr[n] = tile3(n - 2) * 3;
for (int i = 3; i <= n; i++) {
if (i % 2 == 0) {
arr[n] += 2 * tile3(n - i);
}
}
return arr[n];
}