[BOJ 2903] 중앙 이동 알고리즘 - 수학

문제 링크

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

문제 요약

• 정사각형의 각 변의 중앙과 중심에 점을 추가하는 과정을 N번 반복한다.
• 중복되는 점은 한 번만 저장한다.
• N번 후 저장해야 하는 점의 개수를 구한다.

접근 방법

• 각 단계마다 한 변의 점 개수는 2^N + 1이 된다.
• 전체 점의 개수는 (2^N + 1)²로 계산할 수 있다.
• 입력 N에 대해 바로 계산하여 출력한다.

풀이 코드

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    int points = (1 << N) + 1;
    cout << points * points << "\n";
    return 0;
}

시간/공간 복잡도

• 시간: O(1)
• 공간: O(1)