BAEKJOON:2292 벌집

문제

출처 : https://www.acmicpc.net/JudgeOnline/upload/201009/3(2).png

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다. 예제 입력 13 예제 출력 3

해결

첫 번째 방을 기준으로 범위가 늘어나는 경계는 1, 7, 19, 37, 61이다.

그러면 1 + 6 * 1 = 7 7 + 6 * 2 = 19 19 + 6 * 3 = 37 37 + 6 * 4 = 61

으로 6의 배수로 한 겹씩 쌓인다.

바깥 고리의 마지막 번호 찾기

중앙 1을 첫 고리라고 하면 그 밖의 고리에는 방이 차례로 6, 12, 18, …개씩 추가된다. 각 고리의 마지막 방 번호는 1, 7, 19, 37, 61, …이다. 따라서 N이 처음으로 어느 마지막 번호 이하가 되는지 찾으면 중앙에서 지나야 할 방의 수가 된다.

예를 들어 N=13은 7보다 크고 19 이하이므로 셋째 고리에 있다. 중심에서 한 번, 둘째 고리에서 한 번, 셋째 고리에서 한 번으로 총 3개의 방을 지난다. N=7은 둘째 고리의 끝이라 2, N=8은 바로 다음 고리라 3이 된다. 경계 번호 바로 다음 값을 확인하면 부등호가 맞는지 쉽게 검증할 수 있다.

코드는 last에 6×현재 고리 번호를 더하며 바깥 경계를 늘린다. N=1이면 반복에 들어가지 않아 그대로 1을 출력한다. 고리 번호 r까지의 합이 대략 3r²이므로 O(√N)번 반복하고, 변수 몇 개만 써서 O(1) 추가 공간이 든다.

r번째 고리까지의 마지막 번호는 앞선 고리의 증가량 6+12+…+6(r−1)을 더한 값이다. 합을 정리하면 1+3r(r−1)이 된다. 예를 들어 r=5이면 1+3×5×4=61이고, 58은 37보다 크고 61 이하라 다섯 번째 고리에 속한다.

직접 공식을 역산해 제곱근으로 고리 번호를 찾을 수도 있다. 그러나 N의 최댓값 10억에서도 고리를 하나씩 늘리는 반복은 18,257번이므로 단순 반복이 충분하다. 경계 계산은 long으로 해 두어 더 큰 입력으로 확장할 때의 곱셈 오버플로도 피한다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int layer = 1;
        long last = 1;

        while (n > last) {
            last += 6L * layer;
            layer++;
        }
        System.out.println(layer);
    }
}

백준 원문 문제