[이것이 코딩 테스트다] 바닥 공사 with Python

🔒 문제

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

입력

3

출력

5

✅ 해설

• 가로의 길이에 따라 경우의 수를 저장하는 배열 d
  • d[0] = 1
    • 2 x 0 직사각형 바닥을 채우는 경우의 수는 아무것도 두지 않는 경우 즉, 1가지이다.
  • d[1] = 1
    • 2 x 1 직사각형 바닥을 채우는 경우의 수는 1가지이다.
  • d[2] = 1
    • 2 x 1 직사각형 바닥을 채우는 경우의 수는 1가지이다.
• 위와 같은 원리로 d[i]는 2 x i 직사각형 바닥을 채우는 경우의 수를 저장하고 있다.

이때, (i+1) x 2 직사각형 바닥을 채우려면 i x 2 직사각형 바닥을 채운 후, 2 x 1 덮개를 하나 추가하는 방법이 있다.

또, (i-1) x 2 직사각형 바닥을 채운 후, 2 x 1 덮개를 두 개 추가하거나 2 x 2 덮개를 한 개 추가하는 방법이 있다.

위의 세 가지 상황을 고려하여 점화식을 세우면 아래와 같다.

d[ i + 1] = d[i] + d[ i - 1 ] * 2

💻 코드

# 가로의 길이 입력받기
n = int(input())

# 가로의 길이 n에 따라 경우의 수를 저장하는 배열 d
d = [0] * n
d[0] = 1
d[1] = 3

# 경우의 수 구하기
for i in range(2, n):
    d[i] = d[i-1] + d[i-2] * 2

print(d[n-1])