BOJ 2903 - 중앙 이동 알고리즘

문제

정사각형 격자에서 중앙 이동 알고리즘을 N번 수행한 후 점의 개수를 구하라. 매 단계마다 각 정사각형의 변의 중점과 중심에 점을 추가한다.

입력

N이 주어진다 (1 이상 15 이하).

출력

N번 수행 후 총 점의 개수를 출력한다.

예제

입력	출력
`1`	`9`
`2`	`25`

풀이

각 단계마다 한 변의 점 개수가 2배+1이 되는 규칙을 이용하여 공식으로 계산한다.

초기 상태에서 한 변의 점 개수는 2개이다
N번 수행 후 한 변의 점 개수는 2^N + 1개이다
총 점의 개수는 (2^N + 1)^2이다

핵심 아이디어: 매 단계마다 변이 2등분되므로 한 변의 점 개수가 2^N + 1로 증가하며, 전체 격자점은 그 제곱이다.

코드

package day749;
 
import java.io.*;
 
public class Day734BOJ2903중앙이동알고리즘 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    int n = Integer.parseInt(br.readLine());
    br.close();
    System.out.println((int) Math.pow(Math.pow(2, n) + 1, 2));
  }
}

복잡도

시간: O(1)
공간: O(1)

문제