백준 11727번 - C++

#include <bits/stdc++.h>
using namespace std;


// 1. 테이블 정의하기 : D[i]= ix2에서 타일을 붙이는 경우의 수
// 2. 점화식 정의하기 : D[k]=D[k-1]+D[k-2]+D[k-2] // D[k-2]에서 =를 추가하는 방법과 ㅁ을 추가하는 방법
// 3. 초기값 정의하기 : D[1]=1 , D[2]=3


int D[10005];
int mod = 10007;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	D[1] = 1;
	D[2] = 3;
	for (int i = 3; i <= n; i++) {
		D[i] = (D[i - 1] + D[i - 2] * 2) % mod;
	}
	cout << D[n];
}