제한 조건이 있는 경우 제한 조건까지 충족하며 memoization 을
할 수 없는 경우, 제한 조건 없는 것에서 제한 조건 있는 경우를
빼는 방법도 있음.
#define MOD 1000000007
int arr[100];
int cache[101];
int tile(int remain){
if(remain <= 1) return 1;
int &ret = cache[remain];
if(ret != 0){return ret;}
ret = (tile(remain-1)%MOD) + (tile(remain-2)%MOD);
ret = ret % MOD;
return ret;
}
int atile(int remain){
//홀수라면
if(remain %2 ==1){
return (tile(remain) - tile(remain/2) + MOD)%MOD;
}
//짝수 라면
int ret = tile(remain);
ret = (ret - tile(remain/2) + MOD)%MOD;//가운데가 없는 것도 빼고
ret = (ret - tile(remain/2-1) + MOD)%MOD;//가운데가 누워 있는 것도 빼고.
return ret;
}
int main(){
//printf("The Number is %d
",tile(2));
for(int i=0;i<101;i++){
cache[i] = 0;
}
printf("The Number is %d
",atile(2));
for(int i=0;i<101;i++){
cache[i] = 0;
}
printf("The Number is %d
",atile(4));
for(int i=0;i<101;i++){
cache[i] = 0;
}
printf("The Number is %d
",atile(5));
for(int i=0;i<101;i++){
cache[i] = 0;
}
printf("The Number is %d
",atile(92));
return 0;
}