11727번: 2×n 타일링 2

백준 11727번: 2×n 타일링 2

문제링크

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

-

-

---

칸을 채우는 수는 두 가지 경우가 있다.

1. 세로로 막대기 하나를 놓을 때 - 가로 한 칸 차지
2. 가로로 막대기 두개를 놓을 때 - 가로 두 칸 차지 

위의 경우를 더하면서 매번 10007의 나머지 (%연산자)를 해주면 된다.

소스링크