> 벌집 > Bronze II > #[[수학]] ### 문제 요약 ![[Pasted image 20251026120751.png]] 그림과 같이 육각형으로 이루어진 벌집에서, 중앙의 1번 방부터 시작해 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 매깁니다. 방 번호 N이 주어졌을 때, 1번 방에서 N번 방까지 최소 개수의 방을 지나갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산해야 합니다. 정수 N은 10억까지 가능합니다. ### 해설 1번 방을 중심으로 하는 '육각형 층'의 개념을 생각해 보면, 1번 방만으로 구성된 층이 1층이라고 했을 때, N번 방이 k층에 속해 있다면 문제의 정답은 k가 됩니다. k층의 가장 큰 방 번호를 계산해 볼 수 있습니다. 1층은 1, 2층은 1 + 6 = 7, 3층은 1 + 6 + 12 = 19. 이렇게 계차수열 형태임을 짐작할 수 있고 실제로 k층에 대해서는: $1+6\times 1+6\times 2+\cdots+6\times(k-1)=1+3k(k-1)$ 이제 N이 주어졌을 때 $N\le 1+3k(k-1)$을 만족하는 최소의 k를 찾아야 합니다. 여기서는 3가지 방법을 소개합니다. 먼저, 이차부등식의 해를 계산하여 수식 기반으로(closed-form) 즉시 답을 구하는 방법을 생각할 수 있습니다. 위의 부등식을 $3k^2-3k+1-N\ge 0$으로 보고, 양의 근을 사용하면 최소 정수해는 다음과 같습니다: $k=\lceil\frac{3+\sqrt{12N-3}}{6}\rceil$ 그러나 위 방법으로 계산할 때는 부동소수점 오차에 세심한 주의를 기울여야 합니다. 그래서 이를 피하기 위해 매개 변수 탐색(parametric search)의 개념을 도입할 수도 있습니다. k가 양수라는 조건에서는, k가 작을 때는 부등식을 만족하지 않다가 어느 지점에서부터 만족하게 되는 양상을 띕니다. 따라서 부등식을 만족하는 최소의 k를 찾는 문제를 부동소수점에 대한 걱정 없이 이분 탐색으로 풀 수 있습니다. (단, 곱셈 연산에서 일시적으로 int의 범위를 넘길 수는 있습니다.) 그렇지만 이 문제에 대해 이야기할 때 위의 두 풀이 방식은 사실 오버킬(overkill)에 해당하는데요. 그 이유는 $O(\sqrt{N})$ 정도의 시간 복잡도를 가진 단순 반복문 풀이로 문제를 충분히 해결할 수 있기 때문입니다. 이 풀이는 k를 1씩 증가시키면서 $1+3k(k-1)$의 값을 계산해, N이 k층의 범위 안에 들어오는 순간을 찾는 단순한 아이디어를 가집니다. N이 최대 10억이기 때문에, k는 10만을 넘지 않으므로 2초의 시간 제한 안에 문제를 해결할 수 있습니다. ### 배울 점 이 문제를 풀 때 단순 반복문으로 해결하는 것을 떠올리기 쉽지 않다고들 합니다. 저도 일정 부분 동의하지만, 구현의 난이도를 감안했을 때 반복문이 시간 내에 돌 수 있다는 것만 이해하면 Bronze 난이도의 범위를 절대 벗어나지 않습니다. 어떤 방법으로 풀든, 자신의 풀이의 시간 복잡도를 명확하게 추론할 수 있어야 이러한 문제가 눈앞에 던져졌을 때 잘 풀 수 있을 것이라는 생각이 듭니다.