문제
풀이
- 이 문제는 대표적인 타일링 문제로서
DP 알고리즘으로 접근하면 쉽게 구현할 수 있다. - DP 구현을 하기 위해 DP 테이블을 먼저 초기화한다.
| DP | 변의 길이 | 둘레 |
|---|---|---|
| 첫번째 | 1 | 4 |
| 두번째 | 1 | 6 |
| 세번째 | 2 | 10 |
| 네번째 | 3 | 16 |
| 다섯번째 | 5 | 26 |
| 여섯번째 | 8 | 42 |
- 위 테이블에서 확인할 수 있듯이 변의 길이에 따라 출력해야할 둘레가
둘레[i] = 둘레[i-1] + 둘레[i-2]의 규칙을 지키는 걸 확인할 수 있다. bottom-up방식을 이용하여 구현하였다.- 위 점화식을 구현하면 아래와 같다.
코드
# https://www.acmicpc.net/problem/13301
# boj, 13301: 타일 장식물, python3
import sys
input = sys.stdin.readline
def dp(n):
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 81
d[1] = 4
d[2] = 6
# DP bottom-up
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
return d[n]
if __name__ == '__main__':
n = int(input())
print(dp(n))결과
출처 & 깃허브
