[알고리즘 문제해결전략] ASYMTILING - 비대칭 타일링

[생각의 흐름]

1. 전체 타일설치 경우의 수를 구한다.

2. 대칭인 타일설치 경우의 수를 구해서 뺀다.

 

3. 대칭인 타일의 경우의 수를 구하는 방법을 n이 짝수일때 홀수일때로 나눈다.

4. n이 짝수인 경우 다시 두가지 경우로 나눌 수 있는데 하나는 n/2로 대칭인 경우와 다른 하나는 전체 타일 가운데를 2x2타일을 배치한 뒤 절반으로 나누는 방법이다. (n-2)/2

 

n이 홀수인 경우는 자연스럽게 정가운데 타일 하나는 무조건 2x1타일을 배치해야 하기 때문에 (n-1)/2이 된다.

 

5. 타일의 경우의 수를 나눈 뒤 왼쪽 타일만 채워주면 모든 대칭 타일의 경우의 수를 구할 수 있다.

6. modulo연산에서 주의 할 점이 있는데

(전체 타일의 경우의 수 % MOD) - (대칭인 타일의 경우의 수 % MOD) 를 했을 때 음수인 경우가 존재한다.

쉽게 예를 들면(실제로는 이러한 경우는 나오지 않을듯) 전체 타일의 경우의 수는 1000000008개인데 대칭인 타일의 경우의 수는 1000000003개인 경우 음수가 나올 수 있다.

이러한 경우 ((A % MOD) - (B % MOD) + MOD) % MOD를 해줘야한다. (코드 71라인)

해당 내용은 https://foxtrotin.tistory.com/386 를 참고하면 좋을 것 같다.

 

/* https://www.algospot.com/judge/problem/read/ASYMTILING */
#include <stdio.h>
#include <memory.h>

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

long long int cacheSymTile[MAX_N];
long long int cacheTile[MAX_N];

long long int getSymTilingCnt(int n)
{
    if (n < 0)
        return 0;
    if (n == 0)
        return 1;

    long long int &ret = cacheSymTile[n];
    if (ret != -1)
        return ret;

    ret = (getSymTilingCnt(n - 1) % MOD + getSymTilingCnt(n - 2) % MOD);
    ret %= MOD;

    return ret;
}

long long int getTotTilingCnt(int currentPos)
{
    if (currentPos > n)
        return 0;
    if (currentPos == n)
        return 1;

    long long int &ret = cacheTile[currentPos];
    if (ret != -1)
        return ret;

    ret = (getTotTilingCnt(currentPos + 1) % MOD) + (getTotTilingCnt(currentPos + 2) % MOD);
    ret %= MOD;

    return ret;
}

int main(void)
{
    int C;
    scanf("%d", &C);
    while (C--)
    {
        scanf("%d", &n);

        long long int numOfSymTiling = 0;
        memset(cacheSymTile, -1, sizeof(cacheSymTile));
        memset(cacheTile, -1, sizeof(cacheTile));

        if (n % 2 == 0)
        {
            numOfSymTiling = getSymTilingCnt((n - 2) / 2) + getSymTilingCnt(n / 2);
            numOfSymTiling %= MOD;
        }
        else
        {
            numOfSymTiling = getSymTilingCnt((n - 1) / 2);
        }

        long long int totTiling = getTotTilingCnt(0);

        // 전체 타일 경우의수를 구한다음 대칭인 타일의 경우의 수를 빼준다.
        long long int result = (totTiling - numOfSymTiling + MOD) % MOD;
        printf("%lld\n", result);
    }
    return 0;
}