[algospot] ASYMTILING

문제링크 입니다

[ASYMTILING] 문제 😄😄😄😄😄

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

입력

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

출력

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

입력 예제

3
2
4
92

출력 예제

0
2
913227494

전체 코드는 다음과 같습니다.

//
//  ASYMTILING.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/27.
//


#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin("ASYMTILING.txt");
int cache[101];

int TILING2(int n){
    // 기저사례
    if(n<=1){
        return 1;
    }
    else if(n==2) return 2;
    else if(n<1) return 0;
    int &ret = cache[n];
    if(ret != -1) return ret;
    ret = 0;
    ret = ret + (TILING2(n-1) + TILING2(n-2))% 1000000007;

    return ret;
}

int Asymetiling(int n){
    if(n % 2 == 1)
        return (TILING2(n) - TILING2(n/2)+1000000007)%1000000007;
    int ret = TILING2(n);
    ret = (ret - TILING2(n/2)+1000000007)%1000000007;
    ret = (ret - TILING2(n/2-1)+1000000007)%1000000007;
    return ret;
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        int n;
        fin >> n;
        memset(cache,-1,sizeof(cache));
        cout << Asymetiling(n) << endl;
    }
    return 0;
}