백준 2903번 [중앙 이동 알고리즘](C++) -yes6686- 티스토리

 

백준 문제 풀이: 2903 [중앙 이동 알고리즘]

---

문제 링크: https://www.acmicpc.net/problem/2903

문제 설명:

한 점에서 시작하여 정사각형을 계속 분할하는 방식으로 점을 추가하는 알고리즘이 주어진다. 초기에는 정사각형의 각 꼭짓점만 존재하며, 한 단계마다 각 선분의 중점을 연결해 점의 수가 증가한다.

n번째 단계에서 점의 총 개수를 구하는 것이 목적이다. 단계마다 점의 개수는 다음과 같은 점화식으로 유도할 수 있다:

(2n + 1)2

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int k = 1;
    for (int i = 1; i <= n; i++) {
        k *= 2;
    }

    int ans = (k + 1) * (k + 1);
    cout << ans << '\n';
}
  

---

코드 설명

• 핵심 알고리즘: 점화식 유도 – 한 단계마다 한 변에 있는 점의 수가 2ⁿ + 1이 됨
• 구현 세부사항:
  • 처음엔 k=1 (초기 한 변의 간격 개수)
  • 반복문으로 n단계 동안 2배씩 확장
  • 정답은 (k+1)² (정사각형의 점 개수)
• 시간 복잡도: O(n) – n의 범위가 작기 때문에 반복문으로 충분

---

결과

예시 입력:

3
  

예시 출력:

81
  

단계별 점 개수:

• 0단계: 2⁰ + 1 = 2 + 1 = 3 → 3 × 3 = 9
• 1단계: 5 × 5 = 25
• 2단계: 9 × 9 = 81

이 문제는 기하적인 규칙을 수식으로 유도하고 계산하는 연습에 적합합니다. 다른 접근 방식이나 아이디어가 있다면 댓글로 함께 공유해주세요!