문제
접근
DP 문제이다.
타일의 크기는 피보나치 수열과 같다.
타일의 크기에 대한 배열을 n 이라고 하자.
둘레에 대한 배열은 size 라고 하자.
n에 대한 dp는 피보나치와 마찬가지로 n[i] = n[i-1] + n[i-2] 이다.
둘레의 경우 size[i] = size[i-1] + 2n[i] 이다.
이전 둘레에 현재 크기를 두번 더하면 현재 둘레가 된다.
문제의 그림을 보면 이해가 편할 것이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
n = int(input())
dp_n = [1]*(81)
dp_size = [1]*(81)
dp_size[1] = 4
dp_size[2] = 6
for i in range(3, n+1):
dp_n[i] = dp_n[i-1] + dp_n[i-2]
dp_size[i] = dp_size[i-1] + 2*dp_n[i]
print(dp_size[n])