[이코테] 다이나믹 프로그래밍 실전문제 4번

import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 8)
sys.stdin.readline 

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

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

print(d[N])

N의 범위가 1부터 1000까지이므로 d배열을 1001개만큼 설정해주고,

d[1] = 1, d[2] = 3은 직접 그림을 그려보면서 케이스 분류를 통해 알 수 있었다.

만약 1x2 도형을 사용한다면 , 남는 도형은 가로 N-1, 세로 2

만약 2x1, 2x2 도형을 사용한다면 남는 도형은 가로 N-2, 세로 2

따라서 d[i] = d[i-1] + (2*d[i-2])라는 식을 도출해낼 수 있었다.

다이나믹 프로그래밍은 급하게 식을 세우기보단 고민해보면서 관계식을 도출하는 것이 1순위