[TILING2] 문제
2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.
예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.
경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수(C <= 50)가 주어집니다. 그후 C줄에 각각 1개의 자연수로 n(1 <= n <= 100)이 주어집니다.
출력
각 테스트 케이스마다 한 줄에 경우의 수를 1000000007로 나눈 나머지를 출력합니다.
입력 예제
3
1
5
100
출력 예제
1
8
782204094
전체 코드는 다음과 같습니다.
//
// TILING2.cpp
// AALGGO
//
// Created by inhyeok on 2021/09/24.
//
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("TILING2.txt");
int cache[101];
int TILING2(int n){
// 기저사례
if(n==1){
return 1;
}
else if(n==2) return 2;
int &ret = cache[n];
if(ret != -1) return ret;
ret = 0;TIP
ret = ret + (TILING2(n-1) + TILING2(n-2))% 1000000007;
return ret;
}
int main(int argc, const char * argv[]) {
int Test_case;
fin >> Test_case;
int n;
for (int i=0; i< Test_case ; i++){
fin >> n;
memset(cache,-1,sizeof(cache));
cout << TILING2(n) << endl;
}
return 0;
}
Comments