알고스팟: 비대칭 타일링 (ID: ASYMTILING)

[문제 링크]

algospot.com :: ASYMTILING

---

(비대칭 타일수 = 전체 타일수 - 대칭 타일수) 라는 것을 알 수 있다.

n이 홀수라면 가운데 타일이 놓이는 경우가 1개 밖에 없지만, 짝수라면 가운데 타일이 놓이는 경우가 2개 존재한다.

따라서 n에 대한 전체 타일수를 구한 다음,

n이 홀수라면 전체 타일수에 (n / 2)에 대한 전체 타일수를 빼주고,

n이 짝수라면 전체 타일수에 (n / 2)에 대한 전체 타일수와 (n / 2 -1)에 대한 전체 타일수를 빼준다.

위 과정을 통해 결과적으로 양쪽 타일이 대칭인 경우를 제거할 수 있다.

 

 1,000,000,007 을 나눠주기 전에 먼저 한번 더해줘야 한다는 것을 생각하지 못하여 책을 보고 이해하게 되었다.

(만약 1,000,000,008과 1,000,000,006이 있을 때 전자는 나머지 결과 1이라는 값을 가지고, 후자는 1,000,000,006 값을 가지게 되는데 전자와 후자의 차는 2가 정상이지만, 나머지 연산을 거치면서 -1,000,000,005 값을 가지게 되어 오류가 출력될 수 있기 때문. -1,000,000,005에 1,000,000,007을 더해주게 되면 값이 2로 바뀜)

---

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1000000007;
int memo[101];

int tilingCount(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;

	int& ret = memo[n];
	if (ret != -1) return ret;
	return ret = (tilingCount(n - 1) + tilingCount(n - 2)) % MOD;
}
int Solution(int n)
{
	if (n % 2 == 1) return (tilingCount(n) - tilingCount(n / 2) + MOD) % MOD;

	int ret = tilingCount(n);
	ret = (ret - tilingCount(n / 2) + MOD) % MOD;
	ret = (ret - tilingCount(n / 2 - 1) + MOD) % MOD;
	return ret;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		int n;
		cin >> n;
		if (n == 2) 
			cout << "0" << endl;
		else
			cout << Solution(n)<< endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 57 day