[2903] 중앙 이동 알고리즘

난이도: ★★☆☆☆ • solved on: 2025-07-06

---

문제 요약

• 문제 유형: 수학, 구현, 규칙 찾기
• 요구사항: 주어진 단계(n)에 따라 중앙 이동 알고리즘을 적용한 뒤 점의 개수를 구해야 한다.

---

사용 개념

1. 자료구조

   • 없음 (변수만 사용)

2. 알고리즘/기법

   • 점화식
   • 등비수열(기하수열) 규칙 도출

3. 핵심 키워드

   • 패턴 찾기 (pattern finding)
   • 수학적 귀납법 (mathematical induction)
   • 반복적인 도형 확장 (recursive expansion)

---

풀이 아이디어 및 코드

방법 1 : Math.pow()를 이용한 거듭제곱 연산

1. 문제 분해
   • 각 단계마다 한 변의 점 개수를 구하고, 그 제곱을 출력한다.
   • 한 변의 점 개수 = 2ⁿ + 1
   • 총 점의 개수 = (2ⁿ + 1)²
2. 핵심 로직 흐름

   입력 n
   point = (int)Math.pow(2, n) + 1
   출력 point * point

3. 예외 처리
   • n=0일 때 2^0 + 1 = 2+1=3 → 9 (문제 조건과 맞음)

---

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        System.out.print((int)Math.pow(2+(Math.pow(2,n)-1),2));

    }
}

---

방법 2 : 비트 연산자(shift)를 활용한 최적화

1. 문제 분해

• 2ⁿ을 구할 때 Math.pow 대신 비트 시프트 연산(1 << n)을 사용한다.
• 한 변의 점 개수 = (1 << n) + 1
• 총 점의 개수 = ((1 << n) + 1)²

2. 핵심 로직 흐름

   입력 n
   point = (1 << n) + 1
   출력 point * point

3. 예외 처리
   • n=0인 경우에도 올바르게 동작

import java.io.*;

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 point = (1 << n) + 1;
        System.out.print(point * point);
    }
}

---

시간·공간 복잡도

방법 1 :

• 시간 복잡도 : O(1)
• 공간 복잡도 : O(1)

방법 2 :

• 시간 복잡도 : O(1)
• 공간 복잡도 : O(1)

---

어려웠던 점

• 점화식을 빠르게 도출하는 것이 생각보다 쉽지 않았다.
  특히, "한 변의 점 개수"가 등비수열로 증가한다는 점을 직관적으로 파악하는 데 시간이 걸렸다.

---

배운 점 및 팁

• 도형 규칙 문제에서 한 변의 변화 또는 행/열의 개수에 집중하면 점화식 도출이 쉬워진다.
• 비트 연산자는 2의 거듭제곱 계산에서 매우 유용하고, double형 변환 없이 int로 정확하게 값을 구할 수 있다.
• 직접 몇 단계 그려보면서 규칙을 관찰하는 것이 매우 효과적이다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2903
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천) :

  • 2292번 벌집
  • 10250번 ACM 호텔

• 확장 문제 (GPT 추천) :

  • 2630번 색종이 만들기
  • 도형에서 점·변·면의 개수 변화 규칙 찾기 유형의 문제