[실전 문제] beehive

1. 문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다.

 

숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

---

입력

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

출력

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

예제 입력

case 1) 13

case 2) 58

예제 출력

case 1) 3

case 2) 5

 

 

 

2. 풀이

이 문제는 패턴만 알면 쉽게 풀 수 있는 문제다. 우선 아래의 그림처럼 1에서 이동할 수 있는 거리는 다음과 같다.

• 1에서 주황색에 포함된 모든 숫자의 거리는 1
• 1에서 초록색에 포함된 모든 숫자의 거리는 2
• 1에서 파랑색에 포함된 모든 숫자의 거리는 3

 

즉, 

• 2에서 7까지는 모두 1
• 8에서 19까지는 모두 2
• 20에서 37까지는 모두 3

 

이 된다. 13으로 예를 들자면, 13은 초록색 범위인 8에서 19 사이의 값이기 때문에 1에서 13까지의 최단 거리는 2가 된다.

 

그렇다면, 범위를 어떻게 알 것 인가에 대한 생각을 해야한다. 각 색별로 마지막에 끝나는 숫자들을 모아 특징을 찾아보면 다음과 같다.

이 특징을 공식화한다면,

• f(2) = f(1) + 6 x 1
• f(3) = f(2) + 6 x 2
• f(4) = f(3) + 6 x 3
• f(n) = f(n-1) + 6 x (n-1)

 

 

이 되며, 마지막 n-1이 1과의 거리임을 확인할 수 있다. 이를 코드화하면 문제를 해결할 수 있다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

        int prevNum = 1; // 범위의 시작 전 값
        int lastNum = 1; // 범위의 끝 값
        int idx = 1; // 1과의 거리
        while(true) {
            if(n == 1) break; // 찾고자 하는 값이 1일 경우

            lastNum = lastNum + 6 * idx++;
            if(n > prevNum && n <= lastNum) break; // n이 범위내에 있을 경우
        }
        bw.write(idx + "");
        br.close();
        bw.flush();
        bw.close();
    }
}