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

문제

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

정사각형을 계속 분할해서 점을 추가할 때 N번 반복 후 생기는 점의 총 개수를 구하는 문제였다.

문제 풀이

이 문제는 처음에는 2×2 정사각형에서 시작하여, 각 변의 중간에 점을 추가하면서 정사각형을 확장하는 문제이다.

1번 확장하면, 점 3×3개

2번 확장하면, 점 5×5개

3번 확장하면,  9×9개

4번 확장하면,  17×17개

5번 확장하면, 33×33개

이 규칙을 찾아내면, 점의 개수는 (2ⁿ + 1)×(2ⁿ + 1) 형태로 증가한다는 것을 알 수 있다. 규칙을 처음 찾았을때 너무 기뻤다~_~

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());

        int width=(int)Math.pow(2, N)+1; 
        int result=width*width; 

        System.out.println(result);
    }
}