문제링크 : https://www.acmicpc.net/problem/11727
tiling(n+1) = tiling(n) + 2*tiling(n-1)
#include<bits/stdc++.h>
using namespace std;
#define mine
int N;
int dp[1001];
const int MOD = 10007;
int tiling(int n){
if(n == 1) return 1;
if(n == 2) return 3;
int& ret = dp[n];
if(ret != -1) return ret;
return ret = (tiling(n-1) + 2*tiling(n-2))%MOD;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
memset(dp, -1, sizeof(dp));
cin >> N;
cout <<tiling(N)<<endl;
return 0;
}
더해주고 나머지를 구하는것 잊지말아야한다. 또한 만약 빼고 나머지를 구하는 경우 (A-B)%MOD를 구할때는 음수가 나올수도 있으므로 (A-B + MOD) %MOD 로 계산해주어야 한다.