중앙 이동 알고리즘

import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    a = 2
    for _ in range(n):
        a = 2 * a - 1
    answer = a ** 2

    print(answer)


main()

import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    answer = (2 ** n + 1) ** 2

    print(answer)


main()

모든 점의 개수는 전체 정사각형의 한 변에 있는 점의 개수의 제곱과 같음을 관찰할 수 있습니다. 과정을 $n$번 거치고 난 후 한 변의 점의 개수가 $a_n$이라면, 그 다음 과정에서는 $a_n - 1$쌍의 이웃한 두 점 사이에 점이 하나씩 추가되므로 다음과 같이 점화식을 세울 수 있습니다. $$ \begin{align*} a_0 &= 2 \\ a_{n+1} &= 2a_n - 1 \quad (n = 0, 1, 2, \dots) \end{align*} $$ 첫 번째 코드는 이 점화식을 그대로 구현한 것입니다.

위 점화식을 정리하면 다음과 같은 일반항을 얻을 수 있습니다. $$ a_n = 2^n + 1 \quad (n = 0, 1, 2, \dots) $$ 두 번째 코드는 이 일반항을 이용하여 구현한 것입니다.