ASYMTILING(비대칭타일링)

(출처) https://algospot.com/judge/problem/read/ASYMTILING

경우의 수를 구하고 다시 빼주기

해당 문제도 이전 SNAIL 문제와 같이 한 번의 상황에서 생길 수 있는 여러 가지 경우를 나누어 재귀적으로 각각의 경우를 해결한 뒤 다시 합쳐주어 해결할 수 있는 문제이다.

cache[index] == index에서부터 만들 수 있는 타일링의 모든 경우의 수
cache[index] == (가로타일의 경우 + cache[index - 2]) + (세로타일의 경우 + cache[index - 1])

위와 같은 점화식이면 격자의 개수 N이 주어졌을 때 N에 대한 모든 타일링의 경우의 수를 구할 수 있다. 하지만 문제에서 원하는 답은 대칭형태의 타일링은 경우에서 제하고 비대칭형태의 타일링만을 세는 것이므로 구해낸 모든 경우의 수에 대칭형태의 타일링의 경우의 값만 다시 빼주게 된다면 올바르게 정답을 만들어 낼 수 있다.

비대칭형태의 타일링의 경우에도 같은 점화식에서 값을 올바르게 도출해 낼 수 있다.

격자의 개수가 짝수일 때 = 1. 가운데를 중심으로 가로격자가 놓여지고 대칭인 형태 + 2. 그냥 가운데를 중심으로 대칭인 형태 (1) cache[(n / 2) - 1] + (2) cache[n / 2];

격자의 개수가 홀수일 때 = 가운데를 중심으로 세로격자가 놓여지고 대칭인 형태 cache[((n + 1) / 2) - 1]

따라서 cache 메모배열을 한번 완성시키고 난 뒤 나온 경우의 수의 조합만으로도 해당 문제를 간단하게 해결할 수 있다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

int MOD = 1000000007;
int cache[101];

int asymtiling(int n) {
	if (n < 0) return 0;

	int& ret = cache[n];
	if (ret != -1) return ret;
	if (n == 0) return ret = 1;
	

	ret = (asymtiling(n - 1) + asymtiling(n - 2)) % MOD;
	
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		int n;
		cin >> n;
		memset(cache,-1,sizeof(cache));
		int ret = asymtiling(n);
		int ret2 = 0;
		if ((n % 2) != 0) ret2 = cache[((n + 1) / 2) - 1];
		else ret2 = cache[(n / 2) - 1] + cache[n / 2];

		int ret3 = ret - ret2;
		while (ret3 < 0) ret3 += MOD;
		cout << ret3 << "\n";
		
	}
	return 0;
}