다이나믹 프로그래밍 기법
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법.

탑다운 방식
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
바텀업 방식
반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

✅ 문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 x 2의 덮개, 2 x 1의 덮개, 2 x 2의 덮개를 이용해 채우고자 한다.

입력 예시

3

출력 예시

5

➕ 문제 해설

와 같은 바닥의 타일을 왼쪽부터 채운다고 생각하고 점화식을 생각해야 한다.
왼쪽부터 i-1까지 덮개로 이미 채워져 있으면 2 x 1의 덮개를 채우는 겨우는 하나만 존재한다.
왼쪽부터 i-2까지 덮개로 이미 채워져 있으면 1 x 2 덮개 2개를 넣는 경우, 2 x 2의 덮개 하나를 넣는 경우로 2가지가 존재한다.
점화식은 ai = ai-1 + 2 x ai-2 이다.

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]) 

📝 정리

코드를 작성하기 전에 슈도코드로 머리속을 정리하여 문제를 풀었었는데, 다이나믹 프로그래밍은 점화식을 사용하여 문제를 해결할 수 있다. 문제 풀 때 점화식도 고려해야 겠다.