[이코테] 8-4 바닥공사(DP)

정리내용은 [이것이 취업을 위한 코딩 테스트다 with 파이썬] 책을 기반으로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

---

난이도 중하 | 풀이시간 20분 | 시간제한 1초 | 메모리제한 128MB

 

문제

가로의 길이가 N, 세로의 길이가 2인 직사각형의 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2 덮개, 2 X 1 덮개, 2 X 2 덮개를 이용해 채우고자 한다.이때 바닥을 채우는 몯느 겨웅의 수를 구하는 프로그램을 작성하시오.

 

입력 조건
첫째 줄에는 N이 주어진다.(1<=N<=1,000)

 

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

 

코드 구현

import sys

N=int(sys.stdin.readline())

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

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

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