동적 계획법 - 8. 타일링 방법의 수 세기

문제 : 타일링 (난이도 : 下)

 

https://algospot.com/judge/problem/read/TILING2

 

 분석

타일링하는 방법은 다음과 같이 2가지가 나온다.

 

 경우의 수를 셀 때 항상 확인해야 하는 조건이 있다. 위 문제로 예를 들면 다음과 같다.

 

1. 이 두 가지 분류는 타일링하는 방법을 모두 포함해야 한다.

2. 두 가지 분류에 모두 포함되는 타일링 방법은 없다.

 

이 문제는 단계마다 세로 타일 하나로 덮을 것인지, 가로 타일 두 개로 덮을 것인지만 결정하면 된다.

남은 공간이 각각 2x(n-1), 2x(n-2)가 되므로 재귀 호출로 쉽게 답을 구할 수 있다.

 

2xn 크기의 사각형을 타일로 덮는 경우의 수를 반환하는 함수를 tiling(n)이라 할 때, 다음과 같은 점화식이 성립한다.

 

tiling(n) = tiling(n-1) + tiling(n-2)

 

 구현

int MOD = 1000000007;	//나머지로 답을 내는 이유는 overflolw를 피하기위해서 이다.
int cache[101];
// 2xwidth 사각형을 채우는 방법으 수를 MOD로 나눈 나머지를 반환한다.
int tiling(int width)
{
	//base case: width가 1이하인 경우
	if (width <= 1) return 1;
	//memoization
	int& ret = cache[width];
	if (ret != -1) return ret;
	return ret = (tiling(width - 1) + tiling(width - 2)) % MOD;
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		int n;
		cin >> n;
		cout << tiling(n) << '\n';
	}
	return 0;
}