[이것이 코딩테스트다] 다이나믹 프로그래밍(DP) 문제 - 바닥 공사

 

문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 

 

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다. 

 

입력 조건

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

 

출력 조건

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

 

입력 예시

3

 

출력 예시

5

---

문제 풀이

이 문제는 작은 문제를 활용해 큰 문제를 해결할 수 있는 전형적인 DP 문제이다. 

 

마지막에 어떤 덮개를 추가하냐에 따라 점화식을 도출할 수 있다. 

- 마지막에 1x2 타일을 추가하는 경우: dp[n-1]개의 경우에서 1x2 타일 1개 추가 가능 → dp[n-1]

- 마지막에 2x1 타일 2개 또는 2x2 타일을 추가하는 경우: dp[n-2]개의 경우에서 2가지 경우 가능 → dp[n-2] * 2

 

따라서, 점화식은 다음과 같다. 

$dp[n] = dp[n-1] + dp[n-2] * 2$

 

- 초기 조건

> dp[1] = 1

> dp[2] = 3

---

전체 코드

import sys

def tiling(n):
    dp = [0] * (n + 1)  # DP 테이블 초기화
    dp[1] = 1
    if n > 1:
        dp[2] = 3  # N=2일 때 직접 계산

    for i in range(3, n + 1):  # 3부터 N까지 채우기
        dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 796796  # 나머지 연산 적용

    return dp[n]

# 입력 받기
n = int(sys.stdin.readline().strip())
print(tiling(n))