[백준 알고리즘][자바] 2292번 : 벌집

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

2292번: 벌집

 

이번 포스팅은 백준 알고리즘 2292번 : 벌집입니다.

이번 문제는 위를 읽어보시면 알 수 있겠지만, 육각형으로 이루어진 벌집에서 숫자 N이 주어졌을 때

중앙의 1번 방에서 N번방까지 직선으로 몇 개의 방을 지나가는지 구하는 문제입니다. (처음과 끝 포함)

아래의 그림을 보겠습니다.

같은 라인에 있는 숫자들을 연결하여 선을 긋게 되면 중앙의 1을 기준으로

빨간색은 1층, 주황색은 2층, 노란색은 3층, 초록색은 4층.... 이 됩니다.

몇 개의 방을 지나가는지는 결국 주어진 숫자 N이 몇 층에 해당하는 가? 를 구하면 됩니다.

 

그렇다면 주어진 숫자 N이 몇 층인지는 어떻게 구하게 될까요?

각 층별로 숫자의 개수는

1층 - 1개

2층 - 6개

3층 - 12개

4층 - 18개

그리고 각 층의 마지막 숫자들은 1, 7, 19, 37입니다.

이것이 의미하는 바는 각 층의 마지막 숫자는 해당 층까지의 존재하는 방의 개수입니다.

 

예시로 주어진 13이 몇 층인지 구한다면

1층까지의 방의 개수는 1개이기 때문에 해당 안됨

2층까지의 방의 개수는 7개이기 떄문에 해당 안됨

3층까지의 방의 갯수는 19이기 때문에 해당됨

따라서 3층이 정답입니다.

 

이것을 프로그래밍한다면 주어진 숫자 N에 대하여 A(층)을 하나씩 늘려가며 A층까지의 방의 개수보다 N이 작을 때가 N의 층 수이게 됩니다.

 

A층까지의 방의 개수를 구해보겠습니다.

6의 배수로 각 층의 숫자가 늘어나기 때문에 6을 기준으로 식을 분리해줍니다.

1층 - 1개

2층 - 6개

3층 - 12개

4층 - 18개

========

1층까지의 합 - 1 + 6 * 0 = 1

2층까지의 합 - 1 + 6 * 1 = 7

3층까지의 합 - 1 + 6 * 1 + 6 * 2 = 19

4층까지의 합 - 1 + 6 * 1 + 6 * 2 + 6 * 3 = 37

 

4층을 기준으로 식을 정리한다면 - 1 + 6 * (0+1+2+3)

A층까지의 합 - 1 + 6 * (1부터 N-1까지의 합)입니다.

여기서 괄호 안의 부분을 가우스 공식을 이용하여 정리합니다.

가우스 공식은 1부터 N까지의 합을 구하기 때문에 A - 1 층까지의 합을 구한 다음 마지막에 1을 더해줍니다.

A-1층까지의 합 - 1 + 6 * n * (n+1) / 2

 

이제 A-1층까지의 합 공식을 이용하여 코드를 짜줍니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

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

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

		int N = Integer.parseInt(br.readLine()); // 주어진 숫자 N
		int a = 0; // 층 수 (마지막에 1을 더함)
		while(true) {
			if(N <= 1 + 3 * a * (a+1)) { // 주어진 숫자 N이 작을 때 해당 층
				break; // 빠져나옴
			}else { // 아니면
				a++; // 1을 더하면서 검사
			}
		}

		bw.write(String.valueOf(a+1)); // 0부터 시작했기 때문에 1 더함

		br.close();
		bw.flush();
		bw.close();
	}
}