본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임
문제
문제 풀이
DP에서 흔한 문제인 타일링 문제라고 한다. 왼쪽부터 차례대로 덮개를 채운다고 생각해보자.
사용할 수 있는 덮개의 형태가 최대 2x2 직사각형이기 때문에 N-2 미만의 길이에 대해서는 고려할 필요가 없다. 앞서 계산된 결과를 DP 테이블에 저장해가며 진행할 것이다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
# 가로의 길이 정수 n을 입력받기
n = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001
# DP진행(보텀업)
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])
N-2까지 덮개가 채워져 있는 경우(d[i-2]), 경우의 수가 두 개이므로 2를 곱해준다.