바닥공사 : 다이나믹 프로그래밍

<< 점화식 >>

d[i] = d[i-1] + d[i-2]*2

• i-1 : 2x1 하나의 경우만 있음
• i-2 : 2x2 / 1x2(2) -> 2개의 경우가 있음

로직

1. N 입력받기
2. 크기가 1001 인 d를 0으로 초기화
3. d[1] = 1
   d[2] = 3
4. for i in range(3,N+1):
   점화식사용

코드

N = int(input())
d = [0] * 1001

d[1]=1
d[2]=3

for i in range(3,N+1):
  d[i] = (d[i-1] + d[i-2]*2)%796796

print(d[N])

주의할점

• 점화식을 떠올리는 것이 쉽지 않다,,,
  -> 그림을 그리면서 해볼 것 !
• for문 시작점이 3인 것을 주의하자 !
  -> 1과 2는 이미 정의해주었기 때문
  -> d[0]은 0으로 초기화해둔 그대로 둔다