간단하게 DP를 통하여 구현할 수 있는 문제였다.
#include <cstdio>
using namespace std;
int main()
{
int n;
int res;
scanf("%d", &n);
int dp[1001];
for (int i = 0; i < 1001; i++)
{
dp[i] = 0;
}
dp[1] = 1;
dp[2] = 3;
for (int i = 1; i <= n; i++)
{
if (dp[i] == 0)
{
dp[i] = ((dp[i - 1] % 10007) + (dp[i - 2] % 10007) * 2) % 10007;
}
if (i == n)
res = dp[i];
}
printf("%d\n", res);
return 0;
}