바닥 공사

이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.

문제 내용

• 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 바닥이 있음
• 바닥을 $1 \times 2$의 덮개, $2 \times 1$의 덮개, $2 \times 2$의 덮개를 이용해 채우고자 함
• 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성

입력 조건

• 첫째 줄에 N이 주어짐 $(1 \le N \le 1,000)$

출력 조건

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

입력 예시

3

출력 예시

5

문제 해설

• 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있음
  1. 왼쪽부터 $i - 1$까지 길이가 덮개로 이미 채워져 있으면 $2 \times 1$의 덮개를 채우는 하나의 경우만 존재
  2. 왼쪽부터 $i - 2$까지 길이가 덮개로 이미 채워져 있으면 $1 \times 2$ 덮개 2개를 넣는 경우, 혹은 $2 \times 2$의 덮개 하나를 넣는 경우로 2가지 경우가 존재, $2 \times 1$ 덮개 2개를 넣는 경우를 고려하지 않는 이유는 1.에서 이미 해당 경우가 고려되었기 때문
• $i$번째 위치에 대한 최적의 해를 구할 때 왼쪽부터 $(i - 3)$번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없음
• 사용할 수 있는 덮개의 형태가 최대 $2 \times 2$ 크기의 직사각형 형태이기 때문
• 다음과 같이 점화식을 세울 수 있음
  $a_i = a_{i - 1} + a_{i -2} * 2$
• 왼쪽부터 $N - 2$까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채우는 2가지 방법이 서로 다른 것이므로, $a_i$는 $a_{i - 1} + a_{i -2} + a_{i -2}$가 되고 이를 간략히 나타내어 $a_i = a_{i - 1} + a_{i -2} * 2$로 표현

소스 코드

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

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

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

# 계산된 결과 출력
print(d[n])