[python] 백준 11726번: 2*n 타일링

problem

문제링크: https://www.acmicpc.net/problem/11726

알고리즘 : 다이나믹 프로그래밍

입력 - n

solution 

2*n 크기의 직사각형을 2*1 의 타일로 채우는 경우의 수는 n+1 번째의 피보나치수와 같다.

1. dp[] 배열의 1, 2번째에 피보나치수 1, 1 을 할당해둔다.
2. n까지 피보나치 수를 구해 10007로 나눈 나머지 값을 dp의 i 번째에  넣는다. 
3. n+1 까지 피보나치 (수 % 10007) 을 한 값을 구하고 dp[n]을 출력한다.[

[code]

n = int(input())
dp = [1, 1]
for i in range(2, n + 1):
    dp.append((dp[i - 1] + dp[i - 2]) % 10007)

print(dp[n])