[BOJ] 백준 2292번 : 벌집 (JAVA)

문제

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

입력

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

출력

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

 

풀이

수학적 지식을 요구하는 문제였습니다. 하지만 그렇게 어렵지는 않고, 규칙만 잘 찾으면 됩니다.

N이 1일 경우, 초기 값이므로 1을 출력하면 됩니다.

N이 2~7까지 2번째 벌집 줄이므로 2를 출력하면 됩니다.

N이 8~19까지 3번째 벌집 줄이므로 3을 출력하면 됩니다.

이쯤되면 다들 눈치채셨죠? 규칙은 바로 벌집 줄이 6칸씩 증가한다는 사실입니다.

물론, 이러한 규칙도 있지만, 제가 focus를 맞춘 부분은 다름 아닌 범위의 끝 값입니다.

특정 수를 2번째부터 쭉 검사하면서 i번째 벌집 줄의 최댓값보다 작으면 i를 출력하는 방식이죠.

예를 들어 N이 12면 19보다 작으므로 3을 출력하면 됩니다.

따라서 i번째 줄에 해당하는 벌집 방의 최댓값(temp)을 계산하고 N <= temp가 되는 순간을 포착하면 됩니다. N이 temp보다 작거나 같아진다는 것은 N이 i번째 벌집 줄에 해당한다는 말을 의미하기때문이죠.

 

temp를 구하는 방법을 좀 더 보충 설명하자면, temp는 범위의 끝 값이므로 7, 19, 37, 61, ... 으로 증가할 것입니다.

이것을 다시 쓰면, 6 * 1 + 1, (6 * 1 + 6 * 2) + 1, (6 * 1 + 6 * 2 + 6 * 3) + 1, ... 이고, 일반항은 6 * (n * (n + 1) / 2) + 1가 된다는 사실을 알 수 있습니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N = Integer.parseInt(br.readLine());
 
        int i = 1;
        while (true) {
            int n = i - 1;
            int temp = 6 * (n * (n + 1) / 2) + 1;
 
            // N이 temp보다 작다는 말은
            // N이 i번째 벌집 줄에 존재한다는 의미.
            if (N <= temp) {
                bw.write(String.valueOf(i) + '\n');
                break;
            }
 
            i++;
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.