01타일 처럼 문제를 풀어보면 피보나치 수열이다.
#include <iostream>
#include <cstring>
using namespace std;
int N, cache[1001];
int solve(int n) {
if (n <= 2) return n;
int& ret = cache[n];
if (ret != -1) return ret;
ret = (solve(n - 1) + 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;
}