바닥공사 [dynamic Programming] #이것이 코딩테스트다

[문제] 바닥공사: 문제 설명

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다
.태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.
이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어, 2X3 크기의 바닥을 채우는 경우의 수는 5가지이다.

난이도: ●◐○| 풀이시간 20m | 시간제한 1초 | 메모리 128mb

 

<input case>

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000)

 

 

<Output case>

첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

input example	Output example
3	5

<Idea>

Q1. 응어어엄ㅁ어ㅓㅁㅇ머 이게 뭐야 이게 규칙성이 있나?
A 정신차려 친구 다이나믹 프로그래밍은 그리디 알고리즘의 연장선이야 작은 수부터 천천히 해결해나가면 되는거야
Q2. 아 맞아 그럼 작은 수부터 천천히 계산 ->  리스트에 넣기를 반복해나가면 되는거였지 
A. 그치 쉬운 문제니까 천천히 해보자

 

n=int(input())
d=[0]*(n+2)
d[1]=1 
d[2]=3
for i in range(3, n+1): d[i] = (d[i-1] + d[i-2]*2) % 796796 #case 1 남은 칸 수가 1칸이라면 1X2 밖에 등장하지 못함 남은 칸이 2개면 2X2 or 2X1 2개 밖에 등장하지 못함 1X2 2개는 이미 고려했음

print(d[n])