11726번 : 2 x n 타일링

풀이전략

: 규칙성을 찾아라.
a4용지 없이 , 프로그램상에서 그림으로 만들어나가는 연습을 하자.

코드

#include <iostream>
using namespace std;
#include <typeinfo>
#include <string>
#include <algorithm>


int main()
{
	// 2 * 2 만들 수 있는 횟수 : 2
	// 2 * 3 만들 수 있는 횟수 : 3

	// n : 0 -> 공집합 이므로 1로 해야함. 

	// n : 1
	// |
	// |

	// n : 2
	// --
	// --

	// ||
	// ||

	// n : 3
	// --|
	// --|

	// |||
	// |||

	//|--
	//|--

	// n : 4
	// n : 3인 부분에 | 추가함.
	// --||
	// --||

	// ||||
	// ||||

	//|--|
	//|--|

	// n 이 2인 부분에 -- 추가함.
	// ----
	// ----

	// ||--
	// ||--

	// => 결론 : dp[n] = dp[n - 1] + dp[n-2];?? 

	int dp[1001]{0,};
	//점화식 : 2 * n의 직사각형을 만드는 모든 방법의 수는 ? 
	dp[0] = 1;
	dp[1] = 1;

	int n;
	cin >> n;
	for (int i = 2; i <= n; ++i)
	{
		dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
	}

	cout << dp[n];
}