[백준 / BOJ] - 2292번 벌집 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [2292] 

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

문제

 

 

위 그림과 같은 방식으로 벌집의 주소가 정해질 때, 입력받은 방 주소 N은 벌집의 중앙 1번 방에서 몇 개의 방을 거쳐서 갈 수 있는지를 구하는 문제이다.

 

풀이

 

해당 문제도 마찬가지로 단순 반복문을 통한 계산 방식을 통해서는 시간 초과가 발생한다.

해당 방까지의 거리가 어떻게 되는지 규칙을 먼저 찾아야 한다.

2~7까지는 2번만에 이동이 가능하고,

8~19까지는 3번만에 이동이 가능하고,

20~38까지는 4번만에 이동이 가능하다.

 

규칙성은 간단하다, 바깥층으로 나갈 때 마다, 6,12,18,24,30,36식으로 6*Layer식으로 범위가 늘어난다.

이를 활용하여, 6*i의 등비수열의 합을 구하고, 그 합이 입력된 주소보다 크게끔 하는 i를 찾아서 출력해주면 된다. 

 

 

코드

 

#include <iostream>
using namespace std;
int main() {
    int number;
    cin >> number;
    int i = 0;
    for(int sum=2; sum <= number; i++)
        sum += 6*i;
    if(number == 1) i=1;
    cout << i;
    return 0;
}

 

평가

 

규칙을 찾아내고, 등비수열의 합을 활용하는 접근을 할 경우 쉽게 해결할 수 있으나, 규칙을 못 찾게되면 막연한 반복문으로 인해 시간초과가 발생하는 문제이다. 수학 1 카테고리의 문제들은 대부분 규칙성을 찾아야 하는 문제들이기 때문에 단순 반복문으로는 해결할 수 없다는 사실을 감안하고 풀이를 진행하는 것이 좋다.