[DP] 8 - 4 바닥 공사

바닥을 세 종류의 덮개로 채우는 모든 경우의 수를 구하는 프로그램을 작성하라.

예를 들어 2 x 3 크기의 바닥을 채우는 경우의 수는 5가지이다.

 

입력 조건

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

 

출력 조건

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

 

해결 방법

 

1. 왼쪽부터 i -1 까지 길이가 덮개로 이미 채워져 있으면 2 x 1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다. 

2 x 1

i-1

 2. 왼쪽부터 i - 2 까지 길이가 덮개로 이미 채워져 있으면 1 x 2 의 덮개 2개를 넣는 경우, 혹은 2 x 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.

i-2

1 x 2

1 x 2

i-2

 

2 x 2

 

---

# 정수 N를 입력받기
n = int(input())

# 앞서 계산한 결과를 저장하기 위한 DP 테이블 초기화
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])