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

2xn 타일링

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

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

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

예제 입력 1 2
예제 출력 1 2

풀이

세로로 블럭을 채우면 나머지 n-1길이의 직사각형을 채워야하고 가로로 블럭을 채우면 위 또는 아래 어느 곳에 채우든 어쩔 수 없이 2x2크기를 모두 가로로 채우게 되므로 남는 것은 n-2길이의 직사각형이다.

각각의 상황속에서 가장 첫번째 자리에 어떤 방향으로 블럭을 넣을 지 정해야 하고 그 두 가지 모두를 더해야 원하는 답이 나온다.

이를 점화식으로 세우면, D[n] = D[n - 1] + D[n - 2]가 될 것이다.

#include <iostream>
#include <cstring>
using namespace std;

int cache[1001];

int set(int n)
{
	int& ret = cache[n];
	if(ret != -1) return ret;
	else return ret = (set(n - 1) + set(n - 2)) % 10007;
}

int main()
{
	int n;
	cin >> n;

	memset(cache, -1, sizeof(cache));
	cache[1] = 1;
	cache[2] = 2;

	cout << set(n);
	return 0;
}

끝