[백준/Python] 11726 : 2*n 타일링

문제

 

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

---

Algorithm

2 * n 크기의 직사각형을 채우는 방법은 마지막에 2 * 1 타일을 새로로 두는지 가로로 두는지에 따라 달라집니다.

이를 이용해 피보나치 수열과 유사한 점화식을 사용합니다.

 

---

 

 

Code

n = int(input())
dp = [0] * (n + 2)

dp[1] = 1
if n >= 2:
    dp[2] = 2

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007

print(dp[n])