[Softeer] Lv2. 지도 자동 구축 (Java)

1. 문제

• 문제 링크 : Lv2. 지도 자동 구축
• 주제 : Math

---

2. 풀이 과정 및 정리

내가 이 문제에서 핵심으로 잡은 것은 정사각형의 한 변에 포함되어 있는 점의 개수이다.

이 문제는 정사각형의 중앙에 점을 추가하여 작은 정사각형이 또 생겨난다.

그러므로 단계가 올라갈수록 한 변에 포함되어 있는 점의 개수가 증가한다.

1단계와 2단계 전체 점의 개수 표현한 그림

위의 그림은 1단계에서 2단계로 올라갈 때 점의 개수 변화를 나타낸 그림이다.

이 그림을 통해 특징을 생각해보면

• 두 점 사이에 1개의 점이 추가된다. 즉, 한 변에 점 n개가 있을 경우 n-1개의 점이 추가된다.
• 모든 점의 개수는 한 변의 개수의 제곱이다. 즉, n의 제곱이다.

그러므로 나는 한 변의 점의 개수가 어떻게 변하는지에 집중했다.

한 변의 점 개수 변화

1단계 → 2단계

기본 3개의 점이 존재한다.

3 - 1 = 2개의 점을 추가할 수 있다. → 2^1

2단계 → 3단계

기존의 3 + 2 = 5개의 점이 존재한다.

5 - 1 = 4개의 점을 추가할 수 있다. → 2^2

3단계 → 4단계

기본으로 5 + 4 = 9개의 점이 존재한다.

9 - 1 = 8개의 점을 추가할 수 있다. → 2^3

 

위와 같이 단계가 1씩 증가할수록 추가되는 점의 개수는 2, 4, 8 ... 2의 제곱으로 증가한다.

다만 이는 앞 단계 개수에서 증가한다는 것을 기억해야한다.

 

그러므로 현재 단계(n)에서 기본적으로 가지는 점의 개수는 [(n-1)단계의 점의 개수 + 추가할 점의 개수] 이다.

→ 최소 개수부터 단계별 추가할 점의 개수를 계속해서 더해주어야 한다.

n은 최소 1이므로 한 변의 최소 점의 개수(a)는 3이다.

더해주어야할 값은 2의 제곱으로 n-1 제곱까지 더해주면 된다.

int a = 3; //한 변의 점 개수
for(int i = 1; i < n; i++) {
    a += (int)Math.pow(2, i);
}

---

3. 코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        
        int a = 3; //한 변의 점 개수
        for(int i = 1; i < n; i++) {
            a += (int)Math.pow(2, i);
        }

        bw.write(a * a + "");
        bw.flush();
        bw.close();
    }
}