(c++) 백준 "11727) 2xn 타일링2"

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

#include <iostream>

using namespace std;
int dp[1001] = {0,1,3};

int main() {
	int N; cin >> N;
	for (int i = 3; i <= N; i++) {
		dp[i] = (dp[i - 1] + (dp[i - 2])*2)%10007;
	}
	cout << dp[N] << endl;
	return 0;
}