ASYMTILING

#include <iostream>

using namespace std;

const int MAX_N = 101;
const int MOD = 1000000007;

int n;
int cache[MAX_N];

int tiling(int n);

int main()
{
	int caseNum = 0;
	cin >> caseNum;

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin >> n;

		// Initialize
		for (int i = 0; i <= n; i++) cache[i] = -1;

		// Process
		int fullTiled = tiling(n);
		int symmetricTiled = -1;

		if (n == 0 || n == 1 || n == 2) symmetricTiled = n;
		else if (n % 2 == 0) symmetricTiled = (tiling(n / 2) + tiling((n - 2) / 2)) % MOD;
		else symmetricTiled = tiling((n - 1) / 2);

		int ret = (fullTiled - symmetricTiled + MOD) % MOD;

		cout << ret << endl;
	}
}

int tiling(int tileNum)
{
	int& ret = cache[tileNum];
	if (ret != -1) return ret;

	if (tileNum == 0) return ret = 0;
	else if (tileNum == 1) return ret = 1;
	else if (tileNum == 2) return ret = 2;

	ret = (tiling(tileNum - 1) + tiling(tileNum - 2)) % MOD;

	return ret;
}

이번 문제는 전반적으로 쉽게 풀었다. 

( 전체 타일링 경우의 수 ) - ( 대칭인 타일링 경우의 수 ) 를 구하면 답이 나온다.

그럼에도 시간이 오래 걸렸는데 다름아닌 Modulo 연산 때문이었다.

처음에 Modulo 에 관한 처리를 소홀하게 하였는데, 그 결과 n == 92 일 때 결과값이 자꾸 음수값이 나오는 현상이 발생하였다.

(전체 경우의 수) 에서 (부분 경우의 수) 를 마이너스 하였는데 음수값이라니...

이떄 재빨리 알아챘어야 했는데 나는 내 로직이 잘못된 줄 알고 input 값만 계속 추가해가며 테스트하였다.

이 문제에 대한 해결은 ( 전체 경우의 수 ) - ( 대칭인 타일링 경우의 수 )  에다가 "MOD" 값을 더한 후,

다시 그 결과값에 "% MOD" 연산을 수행하는 것이었다.

Modulo는 결과값이 0 ~ (MOD - 1) 의 범위에서 순환하므로 언제든지 음수값이 나올 수 있었다.

이걸 한시간이나 걸려서 알아내다니..................................

컴퓨터와 수학 시간에 공부했던 나는 어디로 간거지..

+) MOD 값이 10^9 + 7 인 이유는

   첫째 32 bit int 형 범위 내에서 표현할 수 있고,

   둘째 소수 이기 때문이다.

AsymTilingInput.txt

AsymTilingOutput.txt