백준 2903번 중앙 이동 알고리즘 (python)

1. 문제

https://www.acmicpc.net/problem/2903

2. 풀이

0일때 4, 1일때 9, 2일때 25 그리고 5일때 1089라는 수가 제곱수란 점에서 힌트를 얻었다.
2, 3, 5, x, y, 33 으로 넘어갔기 때문에 처음에 arr[i - 1] + arr[i - 2] 값일까라는 추측을 했지만, 3번째 갯수를 그려보았을때 81개라는 수가 나오고 알게되었다.

📚 ((math.sqrt(arr[i - 1]) * 2) - 1) ** 2 가 규칙이라는 것을
2 -> 4 - 1 = 3
3 -> 6 - 1 = 5
5 -> 10 - 1 = 9
9 -> 18 - 1 = 17
17 -> 34 - 1 = 33

3. 코드

import math

n = int(input())
arr = [0] * 17

arr[0] = 4
arr[1] = 9
arr[2] = 25

for i in range(3, n + 1):
    arr[i] = ((math.sqrt(arr[i - 1]) * 2) - 1) ** 2

print(int(arr[n]))```