Tri Tiling

http://acm.pku.edu.cn/JudgeOnline/problem?id=2663

Description

In how many ways can you tile a 3xn rectangle with 2x1 dominoes?
Here is a sample tiling of a 3x12 rectangle.

Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30.

Output

For each test case, output one integer number giving the number of possible tilings.

Source

Waterloo local 2005.09.24


Solving

n이 홀수일 때 가능한 모양이 없는 것은 자명하다.

n이 2일 때: 가능한 모양의 갯수는 3개이다.
n이 4일 때: 가능한 모양은 n-2=2일때의 갯수(3) * 3 + 4개가 모여 가능한 모양이 2개 = 총 11개이다.
n이 6일 때: 가능한 모양은 n-2=4일때의 갯수(11) * 3 +  n-4=2일때의갯수(3) * 4개 모양(2) + 6개 모양(2) = 41
n이 8일 때: n-2=6일때의 갯수(41) * 3 + n-4=4일때(11) * 4개 모양(2) + n-2=2일때(3) * 6개 모양(2) + 8개모양(2) = 153
...
위의 연구(?)를 바탕으로 점화식을 새워 DP로 문제를 해결할 수 있다.

#include <cstdlib> #include <cstdio> int main() { int memory[16] = {1}; int n, k; for (n = 1; n <= 15; n++) { memory[n] = memory[n-1]*3; for (k = n-2; k >= 0; k--) memory[n] += memory[k]*2; } while (scanf("%d", &n) > 0) { if (n == -1) break; if (n & 1)printf("0\n"); else printf("%d\n", memory[n/2]); } }