[DP] 다이나믹 프로그래밍 (4) 실전 문제 - 바닥 공사 ⭐

이코테 p.223 실전 문제 - 바닥 공사

입력 예시

3

출력 예시

5

교재 소스코드

• 다이나믹 프로그래밍 기초 예제 중 하나인 타일링 문제 유형
• N = 3 일 경우 바닥을 덮개로 채울 수 있는 모든 경우의 수는 다음과 같음

• 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 다음과 같은 점화식을 세울 수 있음
  • 왼쪽부터 (i - 1)까지의 길이가 덮개로 이미 채워져 있으면 2 x 1 덮개를 채우는 하나의 경우만 존재
  • 왼쪽부터 (i - 2)까지의 길이가 덮개로 이미 채워져 있으면 2 x 2 덮개를 채우는 경우와 1 x 2 덮개를 채우는 경우 총 2가지 존재
  • 따라서 점화식은 a(i) = a(i - 1) + a(i - 2) x 2
• 이를 DP 구현하면 다음과 같음

# 점수 N 입력받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 1001

# 다이나믹 프로그래밍 진행 (바텀업 방식)
dp[1] = 1
dp[2] = 3
for i in range(3, n + 1):
  dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 796796

print(dp[n])