11726번 : 2×n 타일링 - Python

문제

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

풀이

2x1일때
방법은 (|) 1개이다.

2x2일때
방법은 (||), (=) 2개이다.

2x3일때
방법은 (|||), (|=), (=|) 3개이다.

2x4일때
방법은 (||||), (|=|), (==), (||=), (=||) 5개이다.

이정도에서 규칙을 보면
2xn일때는 2x(n-1)에 |를 추가하는 방법 + 2x(n-2)에 =를 추가하는 방법이다.

점화식 : dp[n] = dp[n-1] + dp[n-2]

코드

from sys import stdin, stdout

input = stdin.readline 

n = int(input())

array = [0 for i in range(10000)]

array[1] = 1
array[2] = 2

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

print(array[n]%10007)