[DP] 바닥공사

1. 문제 설명

2 x i  형태의 가로로 긴 타일의 바닥공사를 하려고 한다. 타일의 종류가 1 X 2 / 2 X 1 / 2 X 2 3개일 때, 타일을 까는 경우의 수는 총 몇 개인가?

- 문제의 범위가 정해져있었기 때문에 해당 범위까지만 고려하면 된다.

- 점화식을 만들기 전의 값인 1, 2일 때의 값은 직접 구해줘야 한다.

- i-1일 때 놓을 수 있는 경우의 수는 1개

- i-2일 때 놓을 수 있는 경우의 수는 2개

2. 코드

n = int(input())
df=[0]*(n+1)
df[1] = 1
df[2] = 3 # df[2-1]+1x2, 2x1*2, 2x2*1
for i in range(3, n+1):
    df[i] = (df[i-1]+(df[i-2]*2))%796796 # 문제의 조건
print(df[i])

"""
4
11
> 리스트 값: [0, 1, 3, 5, 11]
"""

3. 코멘트

- 간단한 코드치고는 점화식을 이해하는데 시간이 좀 걸렸었다. (물론, 지금도 완벽히 이해했다고 볼 수는 없을지도...)