[알고리즌 문제] BeeHive

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n == 1) { // 첫번째 방이면 하나의 방을 지나왔으므로 1개를 출력하고 return;
            System.out.println(1);
            return;
        }

        int i = 1;

        while (true) {

            if (n >= (3 * i * i) - (3 * i) + 2 && n <= ((3 * i * i) + (3 * i) + 1)) { // 방 level에 따라 최솟값~최댓값이 존재하는데 입력받은 방(n)이 어느 범위(방)에 속해 있는지 검사.
                break;
            }
            i++; // 방의 level을 제어하는 변수

        }
        System.out.println(i + 1); // 첫번째 방이 아닌이상, 첫번째 방은 기본적으로 건너왔기 때문에 +1
    }
}

1을 기준으로 반시계방향으로 돌면서 벌집이 형성된다. 각 육각형에는 숫자가 존재하는데, 문제는 1에서 n번쨰 육각형까지의 지나가는 방의 최소갯수를 구하는 문제이다.

 

예를 들어, 1번방에서 38번방으로 가기 위한 방법 중 1->2->9->21->20->38으로 가는 방법과 1->7->19->2->38으로 가는 방법이 있다.  전자는 총 5개의 방을 거쳐가지만, 후자는 총 4개의 방을 거쳐간다. 

 

아이디어는, 벌집에서 각 육각형들은 자신이 위치해있는 레벨이 있다. 1은 1레벨, 2~7의 숫자는 2레벨, 8~19는 3레벨.....이 레벨값이 최소한의 경로가 되게 된다. 만약 입력받은 정수n이 어디 레벨에 위치해 있는지만 알 수 있으면 그떄 레벨이 최소 경로가 되게된다.

 

각 레벨의 범위는 2~7, 8~19, 20~37...이 된다. 여기서 각 레벨의 최솟값은 2,8,20,38.... 공차는 6,12,18...6n을 가진다. 이때 최솟값의 일반항은 3n^2-3n+2이다. 최댓값은 7,19,37,61... 공차는 6(n+1)을 가지고 최댓값의 일반항은 3n^2+3n+1을 가진다.

 

결국 입력받은 정수가 위의 최솟값~최댓값 사이에 있는지만 검사해주면 된다. 그리고 입력받은 정수가 1이 아닌 이상, 1번방은 지나왔음을 의미하기 때문에 결과값에는 +1을 더하여 출력해준다.