[Python] 11727. 2xn 타일링 2

n = int(input())

answer = [0 for _ in range(10000)]
answer[1] = 1
answer[2] = 3
answer[3] = 5

for i in range(4, n+1):
    answer[i] = (answer[i-1] + 2 * answer[i-2]) % 10007
print(answer[n])

 

규칙

: 2xn 크기의 직사각형 채우는 방법의 수 = 2x(n-1) 크기의 직사각형 채우는 방법의 수 + 2x(n-2) 크기의 직사각형 채우는 방법의 수 * 2