[백준 / 파이썬] 11726번 2xn 타일링

n = int(input())

d = [0]*(n+2)
d[1] = 1
d[2] = 1

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

print(d[n+1]%10007)

 

2xn 타일링

n=1 : 1

n=2 : 2

n=3 : 3

n=4 : 5

이런 식으로 가다 보면 규칙이 피보나치인 게 보인다

f(n) = f(n-1) + f(n-2) (n>=3)