2292번 벌집

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

 

이번 문제는 아래의 그림 처럼 육각형으로 이루어진 벌집에서

중앙의 1 부터 시작해서 이웃하는 방에 돌아가며 1씩 증가하는 숫자로 번호를 매기는데,

숫자 N이 주어졌을 때 중앙 1에서 부터 N까지 지나가는 최소한의 방의 숫자를 구하는 문제이다.

예를 들어 N = 13 이라면 3개, N = 58 이라면 5개를 지나간다.

 

처음에 이 문제를 보았을때 든 생각은

 

방을 어떻게 처리해야할까 배열을 만들어서 하나씩 생성하고 넘겨짚어야 하나?

아니면 '육각형'이라고 했으니깐 각 블럭마다 6개의 경우의 수가 있다는건데 그럼 어떻게 해야하지?

 

라고 생각하며 이리 저리 그려보다가 '육각형'에서 힌트를 얻어 아래와 같이 그려봤다

지저분 하지만 문제를 해결하는데 도움이 되었다.

 

그러니깐 1을 중심으로 주변의 테두리에 선을 그어서 나무의 나이테 처럼 나눠보았다.

그리고 중심점을 1, 두번째 테두리를 2, 나머지도 3, 4, 5... 이렇게 그려나가니깐 윤곽이 보였다.

또 예제에서 주어진 13과 58의 위치도 정확히 들어맞았다.

 

그러니깐 중심을 기준으로 6개의 블럭이 주위를 애워싸고, 그 2배인 12개의 블록이 다시 한번 둘러싸인 형태이다.

즉, 6 * n 의 형태를 띄고 있다는 사실을 알았다.

 

이제 이걸 코드로 작성하면...

import java.util.Scanner;

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

        int sum = 1;
        int count = 1;

        while(true) {
            if(n <= sum){
                System.out.println(count);
                break;
            }
            sum += 6 * count;
            count++;
        }

    }
}

 

count와 sum은 초기값 1이고, 한번 비교를 할때마다 sum은 6의 배수로 늘어난다.

 

이렇게 또 한 문제를 풀어냈다.