백준 (2292번) - 벌집

백준 (2292번) - 벌집

2292번: 벌집

 

문제

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

입력

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

출력

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

 

입출력 예제

 

설명

• 위에서 설명한 문제는 간단하게 1번 방에서 n번 방까지 가는 거리를 찾는 문제 입니다.  문제를 잘 보면 하나의 규칙을 찾을 수 있는데, 1번방에서 한번의 거리를 이동할 때 벌집의 개수는 6의 배수로 이루어 집다는 규칙 입니다. 이런 규칙에 맞게 임이의 숫자n이 주어지면 1부터 시작해서 6의 배수를 더해가며 거리를 ++  하면 됩니다. 

  (distance)          (checkNumber)

1번방과의 거리        벌집 번호           벌집의 증가 개수 (1번을 제외하고 6의 배수)         

 

         1                       1                        1

         2                    2  ~ 7                    6 

         3                    8  ~ 19                  12

         4                    20 ~ 37                  18

         5                    38 ~ 61                  24

 

위의 조건으로 예제를 풀어보자  n = 18일 때  총 distance를 구해보자.

 

우선 distance = 1;   checkNumber =1;  n=18; 이다.

 

**** 첫번째 반복 ****

1. 벌집 번호(checkNumber) 보다 큰지 확인하고  checkNumber(1) 보다 n(18) 이 크기 때문에 checkNumber의 구간을 다음 구간의 가장큰 값으로 변경한다 <===  ( checkNumber ==  7 )

2. 1번의 결과로 최소 n은 1보다 크다는 걸 알았기 때문에 거리를 +1 한다. <=== ( distance == 2 )

( checkNumber == 7,  distance == 2)

 

**** 두번째 반복 ****

1. 벌집 번호(checkNumber) 보다 큰지 확인하고  checkNumber(7) 보다 n(18) 이 크기 때문에 checkNumber의 구간을 다음 구간의 가장 큰 값으로 변경한다 <===  ( checkNumber ==  19 )

2. 1번의 결과로 최소 n은 7보다 크다는 걸 알았기 때문에 거리를 +1 한다. <=== ( distance == 3 )

( checkNumber == 19,  distance == 3)

 

**** 두번째 반복 ****

1. 벌집 번호(checkNumber) 보다 큰지 확인하고  checkNumber(19) 보다 n(18) 이 작기 때문에 더이상 다음 구간으로 가지않고 반복을 끝낸다.  <=== 이 때 거리는 늘어나지 않고 최종 거리 distance를 출력한다.   결과는 3 

( checkNumber == 19,  distance == 3)

 

이렇게 구간을 6의 배수를 단계별로 더해가면서 해당 구간에 들어가는지 확인해서 거리를 증가 시키는 방법이다. 

혹시라도 n의 값을 한번의 연산으로 거리를 구할 수 있는지 고민을 해봤지만...   결국  패턴을 찾지 못해서  단순하게 풀었다.  혹시라도  더 좋은 답을 보신다면...  댓글로 알려줬으면 좋겠다. ~

 

설명이 엄청나게 길었는데 사실 코드로보면 엄청 짧다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    // 2292번 벌집
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int distance = 1;
        int checkNumber = 1;
        while(true) {
            if(n <= checkNumber) break;
            checkNumber += (distance) * 6;
            distance++;
        }
        System.out.println(distance);
    }
}