[Python]백준 11726번 - 2xn 타일링

1. 문제정보

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

2. 해결전략

타일링은 전형적인 다이나믹 프로그래밍 문제입니다. 길이가 n인 타일을 만드는 방법은 n-1까지 타일을 만드는 방법과 f(n-1)와 n-2까지 타일을 만드는 방법 f(n-2)의 관계를 생각하면 해결이 가능합니다.

 

 

3. 코드

n = int(input())
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%10007)