[백준/Python] 2903 중앙 이동 알고리즘

[백준/Python] 2903 중앙 이동 알고리즘

풀이 코드 및 설명

print((2**int(input())+1)**2)

초기 상태에 4개의 점
각 단계에서 정사각형의 각 변의 중앙과 중심에 새로운 점 추가

초기 상태의 변 1개
다음 단계 2개 .... n 번째 단계에서는 정사각형의 변이 n+1 개이다
즉, 총 점의 수 = (1+2+3+ .... + (N+1))^2 가 된다
위 식은 등차 수열의 합의 제곱과 같다

이를 이용하여 점의 수를 구해보자
각 단계에서 추가 되는 점은 다음과 같다
1. 변에 추가 되는 점 각 변에 총 4n 개의 점이 생기게 된다
2. 중앙에 추가되는 점, 이는 각 단계 마다 1개의 점이 추가된다
총 점의 수는 다음 식과 같다
4 x (1 + 2 + 3 + .... + N) + N이 된다
그럼 N으로 유도하면 다음과 같은 결론을 내릴 수 있다
총 점의 수 = *(2^n + 1)^2 로 구할 수 있다.