[BOJ 2292] 벌집 - 수학

문제 링크

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

문제 요약

• 육각형 벌집에서 중앙 1번 방부터 시작하여 N번 방까지 가는데 지나가는 최소 방의 개수를 구하는 문제

접근 방법

• 수학 / 규칙 찾기
• 벌집의 각 층마다 방의 개수가 6의 배수로 증가하는 패턴을 파악
• 각 층의 마지막 방 번호를 계산하여 N이 속한 층을 찾으면 그것이 최소 거리

핵심 아이디어

1. 벌집의 구조를 층별로 분석:
   • 1층: 1번 방 (1개)
   • 2층: 2~7번 방 (6개)
   • 3층: 8~19번 방 (12개)
   • 4층: 20~37번 방 (18개)
   • k층: 6×(k-1)개의 방
2. 각 층의 마지막 방 번호 규칙:
   • 1층 끝: 1
   • 2층 끝: 1 + 6 = 7
   • 3층 끝: 7 + 12 = 19
   • 4층 끝: 19 + 18 = 37
   • k층 끝: 이전층 끝 + 6×(k-1)
3. N이 어느 층에 속하는지 찾으면 그것이 최소 거리가 됨

풀이 코드

#include <iostream>
#include <string>
#include <vector>

int main() {
    int N(0);
    std::cin >> N;

    // 1번 방은 1층
    if (N == 1) {
        std::cout << 1 << std::endl;
        return 0;
    }

    // 각 층의 마지막 방 번호를 계산하면서 N이 속한 층을 찾는다
    // 1층: 1 (1개)
    // 2층: 1 + 6 = 7 (6개)
    // 3층: 7 + 12 = 19 (12개)
    // 4층: 19 + 18 = 37 (18개)
    // k층: 이전층 + 6*(k-1) (6*(k-1)개)

    int layer(1);
    int maxRoom(1);

    while (maxRoom < N) {
        maxRoom += 6 * layer;
        layer++;
    }

    std::cout << layer << std::endl;

    return 0;
}

시간/공간 복잡도

• 시간: O(√N) - N이 속한 층을 찾기 위해 최대 √N번 정도 반복
• 공간: O(1) - 상수 개의 변수만 사용