2×n 타일링과 비슷하다.
타일이 하나 추가되었고, 따라서 점화식은 이 된다.
#include <iostream>
#include <cstring>
using namespace std;
int N, cache[1001];
int solve(int n) {
if (n < 2) return 1;
int& ret = cache[n];
if (ret != -1) return ret;
ret = (solve(n - 1) + 2 * solve(n - 2)) % 10007;
return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
memset(cache, -1, sizeof(cache));
cout << solve(N);
return 0;
}