[백준/C#] 2xn 타일링 2

2xn 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

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

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

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

풀이

2 x n 타일링의 점화식과 한 가지 차이점이 있다. n-2 길이의 직사각형이 남는 경우가 2가지다. 그러므로 이전의 점화식의 두 번째 항에 2를 곱해주면 된다.

using System;

namespace tile
{
	class tiling
	{
		static int[] cache = new int[1001];
		static int dfs(int n)
		{
			if(cache[n] != -1) return cache[n];
			else return cache[n] = (dfs(n - 1) + 2 * dfs(n - 2)) % 10007;
		}
		
		static void Main()
		{
			int n;
			n = int.Parse(Console.ReadLine());
			for(int i = 0; i < 1001; ++i)
				cache[i] = -1;
			cache[1] = 1;
			cache[2] = 3;

			Console.Write(dfs(n));
		}
	}
}

끝