<백준 Python> 11726 2×n 타일링 실버III

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

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

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

DP를 풀기전 반복되는것, 재귀를 사용하는것. 탑다운(재귀), 바텀업(for문) 인지 구분을 한다.

하단의 그림을 보면 작은것들이 모여 큰것이 만들어짐을 볼수있다 => 이는 곳 드롭탑 방식인것

# 11726번 2×n 타일링

n = int(input())
d = [0] * (10007) 
ans = 0
d[0] = 1
d[1] = 1
d[2] = 2
# 2 * n = 2 * (n -1) + 2 * (n -2)
if n > 2 : 
    for i in range(3,n+1):
        d[i] = d[i-1] + d[i-2]
print(d[n]%10007)