2903번 중앙 이동 알고리즘

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

 

이번 문제는 4개의 점을 가진 정사각형을 둘러싸는 문제이다.

 

먼저 4개의 점을 가진 정사각형의 주변에 3개의 정사각형을 더 둘러싸되 동일한 면은 겹치게 하여 점의 개수를 줄였다.

 

처음 이 그림을 봤을때는 설마 검은  점의 개수를 세라는건 아니겠지 했는데

당연히 그런건 아니고 검은 점은 겹치는 부분을 시각적으로 표시해둔 것이였다.

 

이것도 배열로 풀어야 하나 그럼 어떻게 계산해야하지 고민하면서 노트에 끄적이다가 공식을 찾아냈다.

 

2 + 1 = 3
-> 3 * 3 = 9

3 + 2 = 5
-> 5 * 5 = 25

i + (i-1) = n
-> n * n = reuslt

 

이런 공식이 성립되었다.

그래서 이것을 코드로 다시 풀어내면

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 3;               // 초기값

        for(int i = 1; i < n; i++) {
            result += (result - 1);
        }

        System.out.println(result * result);
    }
}

 

여기서 초기값을 3으로 준 이유는 첫 상태가 하나의 정사각형인 4가 아니고

이미 한번 계산한 후의 정사각형이기에 그 연산은 바로 건너뛰도록 했다.

 

이 문제에서 N의 범위가  (1 ≤ N ≤ 15) 이기 때문에

사실 정답만 안다면 그냥 if문이나 switch문으로 하드코딩 해버려도 정답이 아닐까 생각이 든다.물론 그렇게 하면 이 문제의 의미가 없어지기도 하고 정답을 알정도면 해법도 알고있겠지만 말이다.