문제
문제 : https://www.acmicpc.net/problem/2903
상근이는 친구들과 함께 외계 지형이 필요한 SF 영화를 찍으려고 한다. 외계 지형은 CG로 중앙 이동 알고리즘을 이용해 만들 생각이다. 알고리즘은 다음과 같다.
1. 시작하면서 정사각형을 이루는 점 4개를 고른다.
2. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
3. 정사각형의 중심에 점을 하나 추가한다.
아래 그림은 알고리즘을 2번 거쳤을 때의 모습이다.
알고리즘을 N번 거쳤을 때의 점의 개수를 구하여라.
풀이
먼저 문제 예시를 살펴보면 알고리즘을 1번 거쳤을 때는 한 변의 점의 개수 3개의 제곱이 전체 점의 개수이고, 2번 거쳤을 때는 한 변의 점의 개수 5개의 제곱이 전체 점의 개수에 해당한다는 것을 알 수 있다.
즉, 전체 점의 개수는 한 변의 점의 개수의 제곱에 해당한다. 따라서 알고리즘을 N번 거쳤을 떄의 한 변의 점의 개수를 구하면 전체 점의 개수를 구할 수 있다.
알고리즘을 N번 거쳤을 때의 한 변의 점의 개수를 구해보면 다음과 같다.
즉, 전체 점의 개수는 \( (2^n + 1)^2 \)로 계산할 수 있다.
구현
위에서 구한 공식을 그대로 구현하면 된다.
import sys
n = int(sys.stdin.readline())
print(pow(pow(2, n) + 1, 2))
참고 문서
https://www.acmicpc.net/problem/2903