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

문제해석

2xn 크기 직사각형을 2x1과 1x2로 채우는 경우의 수를 구하자.

점화식 파악

n=1 : 1가지
n=2 : 2가지
n=3 : 3가지
n=4 : 5가지
...

n=n : (n=n-1)가지 + (n=n-2)가지

	int N;
	cin >> N;

	int dp[1000];

	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;

	for (int i = 0; i < N; i++)
	{
		dp[i + 2] = (dp[i] + dp[i + 1])%10007;
	}

	cout << dp[N];