[백준] 11726번: 2×n 타일링 타일링 파이썬

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

11726번: 2×n 타일링

점화식을 생각 못 해내서 우울함

코드는 진짜 간단한데

점화식을 생각 못해냄...

난 바보야..

 

풀이

 

맨 왼 쪽 칸이 1X2 직사각형인 경우 D[i-1]

맨 왼 쪽 칸이 2X1 직사각형 2 개인 경우 D[i-2]

합치면

2Xi 직사각형을 채우는 경우의 수 D[i] 

n = int(input())
D = [0 for _ in range(n+2)]
D[1] = 1
D[2] = 2

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