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

해당 문제 및 해설은 "이것이 코딩테스트 다 with 파이썬" 책을 기준으로 요약 및 정리하여 작성하였습니다.

 

이것이 코딩테스트다 with 파이썬 구입처

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

---

 

문제 : 바닥 공사

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

 

바닥 공사 사진 1

 

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

 

입력 조건

• 첫째 줄에 N 이 주어진다. ( 1 ≤ N ≤ 100 )

 

출력 조건

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

 

입력 예시	출력 예시
3	5

 

해설

 

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

 

바닥 공사 사진 2

 

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

 

바닥 공사 사진 3

 

코드

 

import sys
input = sys.stdin.readline

n = int(input())

# DP 의 기초 세팅 값은 다음과 같이 처리한다.
dp = [0] * 1001

# 다이나믹 프로그래밍 (Dynamic Programming) 진행(바텀업)
dp[1] = 1
dp[2] = 3

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

print(dp[n])

 

 

코드 작성 후 생각

DP 문제를 구현하는 것에서 가장 중요한 것은 점화식을 만드는 것이다. 사실 이번 문제도 만약 위와 같은 공식이 생각나지 않는다면, 직접 개수를 구해보면 된다. N 이 1 일 때, N 이 2 일 때 점점 숫자를 바꿔가며 답을 구해보면 된다. 그렇다면 규칙성을 찾을 수 있을 것이다. DP 는 점화식 이것만 기억해보도록 합시다.