[BAEKJOON] 2×n 타일링 - python

2×n 타일링

알고리즘 - dynamic programming

 
과정:
그림을 그려가며 규칙을 찾아보았다.
아래 그림과 같이 2xn 직사각형을 타일로 채울 수 있다.

arr[2]=2

arr[3]=3

arr[4]=5

arr[5]=8 
...

arr[4]는 'arr[3]에 2x1 세로타일을 추가한 것 + arr[2]에 2개의 1x2 가로타일을 추가한 것' 이 된다.

문제의 규칙은 arr[n] = arr[n-1] + arr[n-2] 이므로 이를 dp로 작성해보았다.

n = int(input())
arr = [1]*(n+1) #array 1로 초기화

for i in range(2,n+1):
 arr[i] = arr[i-1] + arr[i-2]

print(arr[n]%10007)