[Java 코딩테스트] 백준 2292번 문제 풀이 / 백준 벌집 문제

오늘은 백준 벌집 문제를 풀거다. 한번에 맞추지 못했다. 배열 써서 풀려 했는데, 이유 모를 OutOfBounds 오류와 배열 사용으로 인한 메모리 초과 오류가 발생했다. 심지어 정답직전에 테스트 출력까지 포함해버려서 (...) 총 6번의 리트만에 정답... OutOfBounds는 도저히 내 컴퓨터에서 재현이 안된다... 1~10억까지 다 넣어봤는데..난 안난다....

---

벌집 문제

문제를 딱 보면, "... 최소 개수의 방을 지나서 갈 때 ..."로 인해 Shortest Path를 찾는 것인가 싶다.
하지만 그림을 잘 보면, 규칙이 있다.

너무 대충 그렸나?

이 규칙을 찾았으면, 다음 규칙도 보인다.

수열이 보인다!

벌집의 겉에는 원자의 전자껍질과 같은 구조를 발견할 수 있다. 심지어 해당 껍질은 등비수열을 이룬다. 그리고 제일 안쪽 껍질은 무조건 밟아야 함에 착안해서, 두 번째 껍질의 시작을 1로 맞춰주면 문제를 풀기 더 쉽다.
$$ a_n = 6^{(n-1)} $$
벌써 문제를 다 풀어버렸다.

입력값으로 N이 주어지고, 해당 N까지의 거리를 구해야 한다. 껍질의 시작을 1로 맞춰주기로 했으니, 입력값 N에서 1을 빼준다.

N = N - 1 ~> 두 번째 껍질의 시작을 1로 맞춰주기 위함

그리고 껍질의 층 수를 나타내는 변수 base와 껍질을 벗겨내는 반복자를 이용하여 한 층 씩 벗겨내면 된다. 벌집의 방 번호는 항상 양수이기 때문에, 현재 껍질이 음수가 되어서는 안된다.
이를 위한 연산을 입력값과 벗겨낼 껍질 층으로 구할 것이다. 입력 값을 N, 반복자를 i라 할 때, 다음과 같다.

입력 값: N
현재 껍질 수: i
현재 껍질 층: base

다음 껍질 수 i = i + 6 * (base+1);
남은 입력 값 N = N - i

위 내용을 바탕으로 수도코드로 정리하면 이렇게 된다.

WHILE ( N - i >= 0) THEN
i = i + 6 * (base);
base += 1;
END WHILE

이후 While문이 종료되면 base는 입력 값 N에 대한 껍질 층이 반환되고, 이 값은 1로부터 얼마나 떨어져있는지가 된다.

---

최종 코드

import java.util.Scanner; public class Number2292 { public static void main(String[] args){ Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int temp = N-1, base = 1, i = 1; while(temp - i >= 0){ System.out.print("bef: " + i); i += 6 * (base++); System.out.println(", aft: " + i + ", cal: " + temp); } System.out.println(base); } }

결과는 정답!