8.11_비대칭 타일링_ASYMTILING

문제 설명

 

algospot.com :: ASYMTILING

• 타일링 : 2 * n 크기의 직사각형을 2 * 1 또는 1 * 2 (90도 회전) 크기의 직사각형으로 채우기(1 <= n <= 100)
• 대칭 타일링 : 채워진 직사각형의 모양이 좌우 대칭인 경우
• 비대칭 타일링 : 채워진 직사각형의 모양이 좌우 비대칭인 경우

=> 비대칭 타일링의 수를 1,000,000,007로 나눈 나머지를 출력하기

 

 

문제 풀이

1. 전체 타일링 개수 구하기

 

우선, 타일링을 하는 방법으로는

• 세로 직사각형(1*2) 한 개 채우기
• 가로 직사각형(2*1) 두 개 위 아래로 채우기

로 분류할 수 있다.

 

  1번의 경우는 가로 1칸이 채워지고

  2번의 경우는 가로 2칸이 채워진다.

 

경우의 수를 따져보면,

 

   n=1 -> 세로 직사각형 1개

   n=2 -> 가로 직사각형 2개, 세로 직사각형 1 + 1개

   n=3 -> 가로 직사각형 2 + 세로 직사각형 1개, 세로 직사각형 1 + 1 + 세로 직사각형 1개, 세로 직사각형 1개 + 가로 직사각형 2개

 

으로 확인할 수 있는데,

n = 3의 경우에서, (n=2의 경우 * 세로 직사각형 1개를 붙이기) + (n=1의 경우 * 가로 직사각형 2개를 붙이기)임을 알 수 있다.

 

따라서 f(n) = f(n-2) + f(n-1) 으로 전체 타일링의 개수를 구할 수 있다.

 

2. 대칭 타일링 개수 구하기

 

문제에서 요구하는건 비대칭 타일링인데

비대칭 타일링에 대한 규칙은 찾을 수 없지만 대칭 타일링은 직접 만들어낼 수 있다.

 

만약 n=8인 직사각형을 채운다고 할 때,

n=4인 직사각형을 양쪽으로 데칼코마니처럼 찍어내면 대칭 타일링을 구할 수 있다.

 

n이 짝수일 때 대칭 타일링을 만들어내는 방법은 두 가지가 있다.

• 정확히 2등분 하기
• 가운데 가로 직사각형 2개를 걸치기

첫 번째의 경우는 n/2의 경우를 구하면 되지만,

가운데에 가로 직사각형 2개가 걸쳐진다면 절반에서 1칸을 더 사용하므로 (n/2 - 1)의 경우를 구해야 한다.

 

n이 홀수일 때 대칭 타일링을 만들어내는 방법은 한 가지이다.

• 가운데 세로 직사각형 1개를 두기

이 경우에는 n/2의 경우를 구하면 된다.

 

3. 비대칭 타일링 개수 구하기

 

위와 같은 방식으로 구해진 전체 타일링 개수와 대칭 타일링 개수를 활용하여

 

   비대칭 타일링 개수 = 전체 타일링 개수 - 대칭 타일링 개수

 

값을 구할 수 있다.

 

계산 과정에서 메모이제이션을 활용하여

이미 연산한 n개의 직사각형에 대하여 중복연산 하지 않도록 시간을 단축시켰다.

 

 

문제 풀이 코드

/*
	비대칭의 개수 = 전체 개수 - 대칭의 개수
	전체 개수 = n-2의 개수 + n-1의 개수
	대칭의 개수 = n % 2 == 0 ? (n/2의 개수 + n/2 - 1의 개수) : n/2의 개수
*/

#include <iostream>
#include <string.h>

#define DIVNUM 1000000007

int memoization[101];

using namespace std;

int getTilingCount(int num) {
	int& ret = memoization[num];
	if (ret != -1)
		return ret;
	return ret = ((getTilingCount(num - 1) + getTilingCount(num - 2)) % DIVNUM);
}

int main() {
	int C;
	cin >> C; 

	memset(memoization, -1, sizeof(int) * 101);
	memoization[0] = 0;
	memoization[1] = 1;
	memoization[2] = 2;

	for (int tc = 1; tc <= C; ++tc) {
		int n;
		cin >> n;
		// 전체 타일링 개수 구하기
		int totalCnt = getTilingCount(n);
		// 대칭 타일링 개수 구하기
		int symCnt = n % 2 == 0 ? getTilingCount(n / 2 + 1) : getTilingCount(n / 2);
		int result = totalCnt - symCnt;
		cout << (result < 0 ? result + DIVNUM : result) << endl;
	}
	return 0;
}