boj 11762 : 2*n 타일링

문제 주소: https://www.acmicpc.net/problem/11762

난이도: silver 3

1.문제설명

• 2n 크기의 직사각형을 12, 2*1 타일로 채우는 방법의 수를 구해라

2.문제해결 아이디어.

• 기존의 방법에 어떻게 추가를 하면 타일을 채울수 있을까 생각해보자
• 그림 그려서 풀면 알 수 있다.

3.문제접근법

• n-2번째 직사각형 오른쪽으로 세로2개 붙히고, n-1번째 직사각형 오른쪽으로 가로 한개 붙히면된다.
  

4.특별히 참고할 사항

• 그림없이 시도했지만 성공하지 못함
• 처음에는 대칭인것 아닌것으로 나눠서 하려고 했지만
• 단순하게 오른쪽으로 이어 붙힌다고 생각할 경우가 답이였다.

5.코드구현

n = int(input()) # [1,1000]
cache = [1e9] * (1001)
# 2*n타일을 1*2, 2*1 타일로 채우는 방법
cache[1] = 1
cache[2] = 2
for i in range(3,1001):
    cache[i] = cache[i-2] + cache[i-1]
print(cache[n]%10007)