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

# 문제

과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

 

---

 

# 풀이

규칙 찾기 문제!

바로 정답 소스코드를 확인해보자.

 

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);	// 두 표준 입출력 동기화 해제
    
    int dot = 2;
    int n;
    cin >> n;
    
    while(n--) dot = dot*2 - 1;
    cout << dot*dot;
    return 0;
}

 

 

 

규칙을 찾을 때는 아래와 같이 생각했는데

우선 초기 상태는 점 2개 * 2

과정을 1번 거친 후에는 점 3개 * 3

과정을 2번 거친 후에는 점 5개 * 5

그림엔 없지만 과정을 3번 거친 후에는 점 9개 * 9

☞ 각 과정에서의 점의 개수를 제곱해주면 원하는 답을 얻을 수 있다는 걸 알았다.

 

 

while(n--) dot = dot*2 - 1;
cout << dot*dot;

초기 점의 개수는 2로 잡고 단계를 진행하며 점의 개수를 계산 후

(여기서 점의 개수도 2개, 3개, 5개, 9개와 같이 규칙성 있게 늘어나므로 쉽게 계산이 가능하다.) 

dot*dot을 출력해주면 끝!

 

 

 

 

---

 

 

2903번: 중앙 이동 알고리즘