[백준] 11726번 2 x n 타일링, 파이썬

11726번 바로가기

• 그림을 그려보면 수열이 피보나치 형태를 이루고 있음을 알 수 있다

import sys
input=sys.stdin.readline

n=int(input())
def dp(n):
  d=[0]*1001
  d[0]=0
  d[1]=1
  d[2]=2
  for i in range(3,n+1):
    d[i]=(d[i-1]+d[i-2])
  return d[n]
print(dp(n)%10007)