[알고스팟] 타일링 방법의 수 세기 - 동적 계획

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

타일링 방법의 수 세기(링크)

완전 탐색으로 생각한 후 메모이제이션을 적용하자. 각 작업 조각마다 2 x n 사각형의 맨 왼쪽 세로줄을 덮어 나간다. 맨 왼쪽 세로줄을 덮는 방법은 타일 하나를 세워서 놓거나, 두 개의 타일을 가로로 놓으면 된다.

 

타일 하나를 세워서 놓으면 가로의 길이가 n - 1 인 사각형이 남고 두 개의 타일을 가로로 놓으면 가로의 길이가 n - 2 인 사각형이 남는다.

 

2 x 2 인 사각형을 생각해보면 타일 하나를 세워 놓으면 2 x 1 인 사각형이 남고 타일 두개를 놓으면 사각형이 모두 채워진다.

 

따라서, 가로 길이가 1 혹은 0 인 경우에 (세로 타일 한 개를 놓으면 되거나 이미 사각형을 모두 채웠으므로 사각형을 채운 1 가지 방법으로 친다.) 사각형을 채운 방법 1 가지를 찾은 것이므로 1을 반환한다.

 

const int MOD = 1000000007;
int cache[101];
int tiling(int n) {
	if (n <= 1) return 1;

	int& ret = cache[n];
	if (ret != -1) return ret;
	return ret = (tiling(n - 2) + tiling(n - 1)) % MOD;
}