백준 (boj) 파이썬 - 11727 2xN 타일링

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

11727번: 2×n 타일링 2

 

 

 

 

 

 

n이 늘어날수록 당연히 타일링의 방법은 늘어난다. n=4일때 자꾸만 9개의 방법만 떠올라서 문제푸는데 시간이 좀 오래걸렸다. (2x1을 양 옆에 두는경우를 생각 못했다.)

n = 1	1
n = 2	3
n = 3	5
n = 4	11

 

 

 

* 2x1을 양 옆에 두는경우

2x1

2x2

2x1

 

 

점화식

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

 

 

*파이썬 코드

n = int(input())
arr= [1,3,5]

while(True):
    arr.append(arr[-2]*2 + arr[-1])
    if len(arr) > n : break
print(arr[n-1]%10007)