Tiling a Grid With Dominoes

출처 : http://algospot.com/problems/read/GRID

Google Code jam 문제풀다가 Dynamic Programming 벽에 부딫혀서 알고스팟의 DP문제를 물면서 연습도 하고, 감각을 익히려 한다.

• Time Limit: 1000 ms
 
• Memory Limit: 65536 kb

We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled.

Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-by-W grid.

Input Specification

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.

Each dataset contains a single decimal integer, the width, W, of the grid for this problem instance.

Output Specification

For each problem instance, there is one line of output: The problem instance number as a decimal integer (start counting at one), a single space and the number of tilings of a 4-by-W grid. The values of W will be chosen so the count will fit in a 32-bit integer.

Sample Input

3
2
3
7

Sample Output

1 5
2 11
3 781

해법

점화식 세우는 것이 관건.

An, Bn, Cn으로 나누어서 점화식을 다음과 같이 세웠다.
An = A(n-1)+A(n-2)+2*B(n-1)+Cn  : n번째 너비만큼 채우는 방법의 수
Bn = A(n-1)+B(n-1) : n번째 너비만큼 모서리2칸을 비운 나머지를 모두 채우는 방법의 수
Cn = A(n-2)+C(n-2) : n번째 너비만큼 'ㄷ'형태로 채우는 방법의 수
각 점화식의 초항(n=0~2까지)은 간단하기 때문에 손으로 구했다.

int a[1001], b[1001], c[1001];
int size;
a[0]=0;  a[1]=1;  a[2]=5;
b[0]=0;  b[1]=1;  b[2]=2;
c[0]=0;  c[1]=0;  c[2]=1;

in >> size;
for(int i=3; i<=size; i++)
{
 c[i] = a[i-2]+c[i-2];
 b[i] = a[i-1]+b[i-1];
 a[i] = a[i-2]+a[i-1]+2*b[i-1]+c[i];
}

ps. 문제 붙이니까 내 블로그 Grid랑 잘 안맞네;; 다음부턴 링크만 걸어둬야 겠다;