<종만북> 08. 동적계획법_비대칭 타일링 (Asymmetric Tiling) c++

먼저 비대칭 타일링 문제를 풀기 위해서는 앞에서 공부했던 타일링 방법의 수 세는 알고리즘을 복습할 필요가 있다.

2xn 사각형을 채우는 방법들은 맨 오른 쪽이 어떻게 채워져 있느냐로 나눌 수 있다. a는 마지막 타일의 가로길이가 1인 경우, b와 c는 마지막 타일의 가로 길이가 2인 경우이다. a와 c는 본질적으로 동일 하기 때문에

tiling(n)=1xtiling(n-1) + 1xtiling(n-2)와 같은 점화식이 성립한다.

int cache[MAX];
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;
}

비대칭 타일링 문제는 타일링은 대칭이거나 비대칭 이라는 아이디어에서 구할 수 있다. 전체 타일링 방법의 수에서 대칭 타일링의 수를 빼서 얻을 수 있다.

대칭 타일링의 개수를 세는 첫 단계는 n이 짝수인 경우와 홀수인 경우로 나눌 수 있다.

(a)는 n이 홀수인 경우. 대칭이기 위해서는 정가운데 있는 세로줄은 세로 타일 하나로 덮여야만 한다.

(b)와 (c)는 짝수인 경우. (b)는 정가운데 세로줄 둘을 가로 타일로 덮고 나머지가 대칭이고 (c)는 절반으로 나뉜 부분들이 서로 대칭이다.

int asymmetric(int n) {

	if (n % 2 == 1)
		return (tiling(n) - tiling(n / 2) + MOD) % MOD;

	int ret = tiling(n);
	ret = (ret - tiling(n / 2) + MOD) % MOD;
	ret = (ret - tiling(n / 2 - 1) + MOD) % MOD;

	return ret;
}

*여기서 +MOD를 해주는 이유는 tiling()이 MOD로 나눈 나머지를 반환하기 때문에 실제 경우의 수가 양수라도 두 수를 뺀 값은 음수일 수 있기 때문이다.