바닥 공사-[이것이 취업을 위한 코딩 테스트다]

📖 문제

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

입력 조건

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

출력 조건

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

My answer

import sys 
input=sys.stdin.readline

n=int(input())

d=[0]*(n+1)

d[0],d[1]=1,1

for i in range(2,n+1):
    d[i]=(d[i-2]*2+d[i-1]) % 796796

print(d[n])

 

풀이

우선 dp문제를 풀기위해서는 살짝의 노가다를 해봐야한다. 경우의 수를 몇개 시도하면서 규칙을 찾으면

위와 같이 d[i]=d[i-2]*2+d[i-1]이 나오게 되는데, 이 식은 아래 그림과 같은 이유로 도출된다.

이번에 구성해야할 타일의 가로를 N이라고 가정했을 때, 이 N은 첫번째 그림에서 볼 수 있듯이, N-1을 구성한 그림에다가 긴 짝대기 하나를 붙이는 경우의수와 같고, N-2를 구성한 그림에다가 길이가 2짜리 타일을 추가해야하므로 2,3번쨰 그림처럼 2개가 더 있다. 

 

위 그림은 규칙을 찾기위해 노가다 한 모습이다. 

 

자신의 풀이가 맞는지 확인하려면 백준의 2*n타일링에다가 나누는 숫자만 바꿔서 테스트해보길 바란다. 

11727번: 2×n 타일링 2

아래 백준 2xn 타일링 2를 풀이한 링크이다. 그림을 보며 이해하면 쉬울 것 같다. 

 

[Python] 백준 #11727- 2xn타일링 2