[백준] 2292번 : 벌집

현재 위치 1을 포함하여 N까지 가기 위한 최단 경로를 구하는 문제다.

 

벌집은 6각형으로 이루어져있으니

밖으로 한 층 나갈 때마다 6의 배수만큼 방의 개수가 증가한다

 

아래와 같이 방의 개수가 증가한다.

1 + 6 = 7

7 + 12 = 19

19 + 18 = 37

...

 

즉 최단 경로만 구하면 되는 문제이기 때문에

한 층씩 나갈 때마다 현재 층에 N이라는 방이 있는지 확인만 하면 된다.

 

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();

        int now = 1;
        int count = 1;

        while (now < n) {
            now += 6 * count;
            count++;
        }

        System.out.println(count);
    }
}

 

시작 위치는 항상 1이기 때문에 현재 위치를 1로 지정해주고

현재 위치도 이동한 것으로 포함하기 때문에 이동 횟수도 1부터 시작한다.

 

현재 위치한 층의 방이 n보다 작을 때까지 반복하며

방의 개수를 더해주다보면 반복문을 탈출한 시점의 층에 찾는 방이 있다.