[11727] 2xn 타일링 2

• 입력: 가로 n
• 출력: 2x1, 2x2 타일을 이용하여 2xn 타일을 나타낼 수 있는 경우의 수
• 알고리즘: 동적 계획법, 피보나치 수열
• 소스코드


#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; int main() { int n; scanf("%d", &n); vector<int> tile(n + 1); tile[1] = 1; tile[2] = 3; for (int i = 3; i <= n; i++) tile[i] = (tile[i - 2] * 2 + tile[i - 1]) %10007; printf("%d\n", tile[n]); return 0; }

2xn 타일링 1 문제와 같이 이는 피보나치 수열을 사용해야 한다. 단, 점화식이 다르다.

2xn의 경우, An = An-1 + An-2이다. 이유는 2x(n - 2) 경우의 수에 2x1를 뒤에 붙이는 경우의 수와 2x(n - 1) 경우의 수에 2x1 가로 두 개로 뒤에 붙이는 경우기 때문이다.

이 문제는 위 경우에서 2x2를 나타낼 수 있는 경우의 수가 2x1 가로 두 개와 2x2 정사각형 하나, 총 두 개이므로

2x(n-2)로 2xn을 만들 수 있는 경우의 수는 곱하기 2이다.

즉, 점화식은 An = An-2 * 2 + An-1이다. 

• 문제 참조: https://www.acmicpc.net/problem/11727