[BaekJoon 2292][🟤2] 벌집

❓ 문제

백준 2292 - “벌집”

🎯 난이도

Bronze 🟤2

🧠 풀이

1. 내 풀이 (규칙 찾기)

- 알고리즘

• Mathematics

- 설명

특정 규칙을 찾아내어 그 규칙에 따라 반복문을 돌며 답을 찾아내는 방식으로 풀었다.

방 하나가 육각형 모양에 시계 방향을 돌며 방이 하나씩 늘어나는 구조이다. BFS도 생각해 봤지만 너무 복잡할 것 같았고, 그래프를 이용한 방식도 힘들어 보여서 결국은 어떠한 규칙을 찾는게 맞는 것 같다는 생각을 했다.

규칙은 생각보다 단순하다.

바깥 레이어가 한 겹 늘어날 때마다 늘어가는 방의 갯수가 6개가 더 생긴다.

즉, 각각의 레이어의 방의 갯수를 세어보면 다음과 같다.

1. 1 레이어 : 1개 (1)
2. 2 레이어 : 7개 (1 + 6)
3. 3 레이어 : 19개 (7 + 12)
4. 4 레이어 : 37개 (19 + 18)

그리고 이는 각 레이어의 가장 높은 숫자의 방을 의미하기도 한다.

따라서 이 규칙에 따라 찾으려는 방의 숫자가 어떤 범위의 레이어에 속하는지만 알아내면 답이 나온다.

시간 복잡도는 O(√N)인데 각각의 레이어의 수만큼만 반복을 돌면 되기 때문이다. 이해가 잘 안된다면 추가 풀이 1 을 참고하면 된다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

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

    int iN{};
    cin >> iN;

    int iEnd{ 1 };
    int iCnt{ 1 };

    while(iEnd < iN)    // 누적합 구하기
    {
        iEnd += 6 * iCnt;
        ++iCnt;
    }

    cout << iCnt;

    return 0;
}

---

2. 추가 풀이 (규칙 + 수식화)

- 알고리즘

• Mathematics

- 설명

위의 규칙을 '수식'으로 '공식화'해 바로 답을 찾아낼 수 있게끔 하는 풀이이다.

규칙을 공식화하는 과정은 다음과 같다.

• n번째 레이어까지의 누적 방 개수는 다음과 같다.

\[ end(n) = 6(1 + 2 + 3 + 4 + \cdots + (n - 1)) \]

• 등차수열의 합 공식을 사용하고 대입하면,

\[ 1 + 2 + 3 + \cdots + (n - 1) = \frac{(n - 1) n}{2} \]

\[ end(n) = 1 + 6 \cdot \frac{(n - 1) n}{2} = 1 + 3n (n - 1) \]

• 따라서 N이 몇 번째 레이어에 속하는지를 다음과 같이 표현할 수 있다.

\[ N \le 1 + 3n (n - 1) \]

• 이를 2차 방정식으로 변형하고 근의 공식을 쓰면 n을 구할 수 있다.

\[ 3n^2 - 3n + 1 - N \ge 0 \]

\[ n = \frac{3 \pm \sqrt{12N - 3}}{6} \]

• 또한 양수만 필요하므로 최종적으로는 다음 식이 된다.

\[ n = \frac{3 + \sqrt{12N - 3}}{6} \]

이렇게 구하는 n의 값은 N이 정확히 마지막 방의 숫자가 아닐 경우에 중간값이 나오므로, ceil로 올림을 해서 구하는 값이 최종 답이 된다.

수식을 이용해 한 번에 바로 답을 찾아내는 것이므로 O(1)의 아주 빠른 시간 복잡도로 해결할 수 있다.

- 코드

추가 풀이 코드

#include <iostream>

#include <cmath>


using namespace std;

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

    int iN{};
    cin >>  N;

    // 최대한 오차를 줄이기 위해 범위가 큰 long double을 사용
    long double ldNum = (3.0L + sqrtl(12.0L * iN - 3.0L)) / 6.0L;

    // long double 사용했으므로 ceil도 이에 맞춰 ceill로 사용
    cout << static_cast<int>(ceill(ldNum));

    return 0;
}

---

💭 후기

규칙까지는 문제 없이 찾을 수 있는데, 이를 수식으로 공식화까지 할 수 있다는 부분이 흥미로웠다. 앞으로도 어떠한 규칙을 찾으면 비슷한 방식으로 공식화해서 O(1)의 시간으로 줄일 수 있는 방법을 고민해보면 좋을 것 같다.