백준 11726번 2xn 타일링

해당 문제는 매우 쉬운 DP 문제이다.
2xn 크기의 직사각형의 타일을 채우기 위해서 1x2, 2x1의 타일을 사용할 수 있다.
사실 2x1은 혼자서 사용 못하기때문에 2x2 타일이라고 생각하면 편하다.
결국 이 문제는 n을 1과 2를 이용해서 만들라는 문제이다.

예를들어 5를 만들때는 (1,1,1,1,1),(1,1,1,2),(1,1,2,1),(1,2,1,1),(2,1,1,1),(1,2,2),(2,1,2),(2,2,1) 의 경우가 나오는데

이는 3을 만드는경우에 2크기의 타일을 더해주는 것과 4을 만드는 경우에 1크기의 타일을 더해주는 것의 합이다.
결국 아래와 같은 점화식이 나온다.

dp(n)=dp(n-1)+dp(n-2)

크기가 매우 커져서 문제에서 10,007로 나누라는 조건이 주어지니 놓치지 말자.