백준 2292번 [벌집](C++)-yes6686- 티스토리

백준 문제 풀이: 2292 [벌집]

---

문제 링크: https://www.acmicpc.net/problem/2292

문제 설명:

벌집 구조에서 주어진 방 번호 N까지 도달하기 위해 거쳐야 하는 최소 방 수를 구하는 문제입니다.

• 중심 방(1번 방)부터 시작하여 각 층마다 방의 개수는 6씩 증가합니다.
• 예를 들어, 첫 번째 층에는 1개의 방, 두 번째 층에는 6개의 방, 세 번째 층에는 12개의 방이 있습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    if (N == 1) {
        cout << 1 << endl;
        return 0;
    }

    int cnt = 1; // 중심 방에서 시작
    int layer = 1; // 벌집의 현재 층
    while (N > cnt) {
        cnt += 6 * layer; // 각 층의 방 개수는 6의 배수로 증가
        layer++;
    }

    cout << layer << endl;
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 중심 방에서 시작하여 N번 방까지의 최소 거리를 계산합니다.
• 구현 세부사항:
  • 방 번호 N이 현재 층의 마지막 방 번호보다 크면 다음 층으로 이동합니다.
  • 현재 층에서 거쳐야 하는 방 개수는 중심 방에서 시작해 6씩 증가합니다.
  • 층 수(layer)를 증가시키며 방 번호 N을 포함하는 층을 찾습니다.
• 시간 복잡도: O(√N), 방 번호가 특정 층에 포함되는지를 확인하는 데 걸리는 시간

---

결과

주어진 방 번호 N까지 도달하기 위해 거쳐야 하는 최소 층 수를 출력합니다. 각 층의 방 개수가 6씩 증가하는 규칙을 활용해 효율적으로 계산했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!