백준 11727 : 2 x n 타일링 2

#include <iostream>
using namespace std;

int main()
{
int n;
cin >> n;
int dp[1001] = { 0 };
dp[1] = 1;

for (int i = 2; i <= n; i++) {
if (i % 2 == 0)
dp[i] = (dp[i - 1] * 2 + 1) % 10007;
else
dp[i] = (dp[i - 1] * 2 - 1) % 10007;
}

cout << dp[n];
return 0;
}

점화식은 간단하고

if (i % 2 == 0)
dp[i] = (dp[i - 1] * 2 + 1) % 10007;
else
dp[i] = (dp[i - 1] * 2 - 1) % 10007;
i가 짝수홀수 일때 다르게 써주면 된다.