(Python) - BOJ(11727번) : 2 x n 타일링 2

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

11727번: 2×n 타일링 2

---

• 문제 : 

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

 

 

---

• 풀이 :

그림을 그려가며 규칙을 찾았는데  

 

f(n) = f(n-1) + (f(n-2) * 2)

 

라는 점화식이 도출되었다.

이를 구현하면 된다.

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    N = int(input())
    dp = [0,1,3]
    for i in range(3,N+1):
        dp.append(dp[i-1] + dp[i-2] * 2)
    print(dp[N]%10007)