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

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

2903번: 중앙 이동 알고리즘

 

1. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
2. 정사각형의 중심에 점을 하나 추가한다.

정사각형에 위의 중앙 이동 알고리즘을 n번 적용하였을 때

추가된 점의 개수를 중복 없이 구하는 문제다.

 

개인적으로는 문제의 이해보다는 그림을 보고 규칙을 찾아서 풀었다.

 

주어진 그림 예시를 살펴보다 보니 

한 줄의 사각형의 수는 이전 사각형의 개수의 2배로 증가하는 규칙이 있다.

 

중앙 이동 알고리즘을 적용하기 전의 초기 상태는 사각형이 하나라면

그 뒤는 2 > 4 > 8 > 16 > 32 > ... 순서로 증가한다.

 

또한 한 줄에 찍히는 점의 수는

한 줄에 존재하는 사각형의 수  + 1이고

가로와 세로 상관 없이 찍히는 점의 수는 같으니

(한 줄에 존재하는 사각형의 수  + 1)의 제곱이

중복을 제외한 점의 수가 된다.

 

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();

        int count = 1;

        for(int i = 0; i < n; i++) {
            count *= 2;
        }

        System.out.println((count + 1)*(count + 1));
    }
}