[백준 - 11726] 2×n 타일링

문제

문제읽기

2xn의 직사각형을 1X2, 2X1 타일로 채우는 방법의 수를 구하는 프로그램을 구하시오.

이는 마주보고 앉은 사람들이 연속되지 않게, 건너편 사람 혹은 옆사람과 악수를 한 번만 하는 경우로도 볼 수 있다.

문제풀이

해당 결과를 살펴보면,

n	경우의 수
1	1
2	2
3	3
4	5
5	8

과 같이 진행된다.
즉, 점화식에 해당하는 Array[n] = Array[n-1] + Array[n-2]
를 구할 수 있다.

n = int(input())
# 초기값 세팅
array = [0] * 1001
array[1] = 1
array[2] = 2

for x in range(3, n+1):
    array[x] = (array[x-1] + array[x-2]) % 10007
    
print(array[n])