[백준] 2903번 : 중앙 이동 알고리즘 | C++

1. 문제 상세

 

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

 

 

 

2. 문제 접근

 

과정에 따른 점의 개수의 규칙을 보면 4, 9, 25, 81, ... 와 같이 2, 3, 5, 9, ... 의 제곱으로 이루어진다.

2, 3, 5, 9 ... 은 각 과정에서 한 변에 위치한 점의 개수들이 된다.

결과적으로 각 과정에서 모든 점의 개수는 한 변의 점 개수의 제곱이 된다.

 

이제 초기상태부터 과정을 거칠 때 마다 한 변의 점의 개수가 몇 개인지만 알아내면 된다.

처음엔 2개, 과정을 1번 거칠 시 3, 2번은 5, 3번은 9, ...

여기서 증가하는 수를 보면 이전 과정의 한 변의 점 갯수 + (이전 과정의 한 변의 점 갯수 - 1) 이다.

즉 2, 2+(2-1) = 3, 3+3(-1) = 5, 5+(5-1) = 9, ..이렇게 증가한다.

 

이제 규칙을 알았으니 과정을 반복할 횟수를 입력받아 점의 개수를 계산하자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int n, l_point = 2, point;
    
    cin >> n;
    
    for(int i = 0; i <= n; i++) {
        point = l_point * l_point;
        l_point += l_point - 1;
    }
    cout << point << endl;
}

 

정수형 변수 n, l_point, point 를 선언하고 l_point 를 2로 초기화한다.

 

cin으로 정수(과정)를 입력받아 n 에 저장한다.

 

for문으로 i 가 0부터 n 보다 작거나 같을 때 까지 1씩 더하며 반복하도록 한다.

point 에 l_point 의 제곱 값을 저장한다.

l_point 의 값에 l_point 에서 1을 뺀 값을 더해준다.

 

반복이 끝나면 point 를 출력한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

가끔은 너무 복잡하게 생각하지 말고 수의 규칙을 찾아보자.