[파이썬] [DP] 8492. 바닥 공사 1

로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 복도가 있습니다.

 

태혁이는 이 복도의 바닥을 1 X 2의 타일와 2 X 1의 타일을 이용해 채우고자 합니다.

단, 타일을 겹쳐 놓거나 타일을 작게 쪼갤 수 없습니다.

 

바닥을 타일로 가득 채우는 방법의 수를 출력하는 프로그램을 작성하세요.

 

예를 들어 가로의 길이가 3, 세로의 길이가 2인 경우 바닥을 채우는 방법은 총 3가지이므로 3을 출력해야 합니다.

 

입력값 설명

복도의 가로 길이를 뜻하는 정수 N이 주어집니다. (1 ≤ N ≤ 1,000)

 

출력값 설명

가로의 길이가 N, 세로의 길이가 2인 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력합니다.

 

예제 입력1

3

예제 출력1

3

예제 입력2

5

예제 출력2

8

 

---

전형적인 DP문제 기본 DP문제 절대 잊지 말아야할 DP문제 

간단하게 

N=1 : 1

N=2 : 2

N=3 : 3

N=4 : 5 

N=5 : 8

임을 알 수 있다.

점화식을 풀어 규칙을 알아 낼 수 있다 -> DP 

import sys 
input = sys.stdin.readline


if __name__=="__main__":
    N=int(input())
    dp = [0]*1000
    dp[1] = 1
    dp[2] = 2
    for i in range(3,N+1):
        dp[i] = (dp[i-2] + dp[i-1]) % 796796
    
    print(dp[N])