[알고스팟] ASYMTILING 비대칭 타일링

문제

그림과 같이 2 n 크기의 직사각형을 2 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 좌우 대칭이어서는 안 됩니다. 위 그림은 2 * 5 크기의 직사각형을 채우는 비대칭 타일링 방법 6가지를 보여줍니다. 다음의 2가지는 좌우대칭이기 때문에 세지 않습니다.

n 이 주어질 때 가능한 비대칭 타일링 방법의 수를 계산하는 프로그램을 작성하세요. 방법의 수는 매우 클 수 있으므로, 1,000,000,007 로 나눈 나머지를 출력합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 그 후 각 줄에 사각형의 너비 n (1 <= n <= 100) 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지를 출력합니다.

예제 입력

3
2
4
92

예제 출력

0
2
913227494

Concept

동적계획법 문제로 나온 문제이지만, 최대한 수학으로 간결하게 풀고 싶었다.
공식을 도출하는데 시간 소요가 컸다.

Code

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

long long cache[101][101];

long long combi(long long n, long long r) {
    if (cache[n][r] != 0) return cache[n][r];

    if (r == 1) return n;
    else if (n == r || r == 0) return 1;
    cache[n][r] = (combi(n - 1, r - 1) % 1000000007 + combi(n - 1, r) % 1000000007) % 1000000007;
    return cache[n][r];
}

int main() {
    long long c, n;

    cin >> c;
    for (long long i = 0; i < c; i++) {
        cin >> n; // 7일 때
        long long two, one, result = 0;
        two = n / 2; // 3
        for (long long j = two; j >= 0; j--) {

            one = n - 2 * j;
            long long temp = combi(one + j, j);

            // 대칭인 경우의 수 빼기 (짝C짝, 짝C홀, 홀C짝, 홀C홀 로 case분류 가능)
            if ((one + j) % 2 == 0 && j % 2 == 0) temp -= combi((one + j) / 2, j / 2);
            else if ((one + j) % 2 == 0 && j % 2 == 1)  temp -= 0; 
            else if ((one + j) % 2 == 1 && j % 2 == 0) temp -= combi((one + j) / 2, j / 2);
            else if ((one + j) % 2 == 1 && j % 2 == 1) temp -= combi((one + j) / 2, j / 2); 
           
            result += temp % 1000000007;
            
             
        }
        cout << result % 1000000007 << endl;
    }

}

Comment

if문에서 if ((one + j) % 2 == 0 && j % 2 == 0)로 써야하는 걸 if (one + j % 2 == 0 && j % 2 == 0)로 작성하여 오류 원인 찾는데 시간 낭비가 심했다.
수학적인 접근이 시간 단축이 꼭 도움이 되는 것 같지는 않다.