[백준/Python] 2292 - 벌집

문제

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

입력

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

출력

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

풀이

설계

'수학' 부분은 내가 늘상 그렇듯 코드로 구현하는 것보다 규칙을 찾아내는 게 더 어렵다. 일단 방의 개수 혹은 방 숫자에 규칙이 있을 것으로 생각하고 분석해 보았다.

1. 중앙의 방 개수는 1개, 1번째 줄의 방 개수는 6개, 2번째 줄의 방 개수는 12개, 3번째 줄의 방 개수는 18개, 즉 각 줄의 방 개수는 6 * n의 형태를 띤다.
2. 중앙의 방을 가기 위해서는 1개의 방을, 1번째 줄의 방(2~7번 방)에 가기 위해서는 2개의 방을, 2번째 줄의 방(8~19번 방)에 가기 위해서는 3개의 방, 3번째 줄의 방(20~37번 방)에 가기 위해서는 4개의 방을 지난다. 즉, 지나야 하는 방의 개수는 n과 동일하다.
3. 1과 2를 이용해 각 줄별로 번호의 최댓값을 찾으면 다음과 같은 규칙을 유도할 수 있다.
   1 + 6 * cnt(1) = 7 ... max1
   max1 + 6 * cnt(2) = 19 ... max2
   max2 + 6 * cnt(3) = 37 ... max3
4. cnt를 1로 설정한 뒤 n이 1이면 cnt를 그대로 반환하고, n이 2 이상인 경우 n의 값을 각 줄의 최댓값(max(n))과 비교하여 그보다 크다면 cnt를 1씩 증가시킨 뒤 다시 최댓값과 비교한다. 그리고 n이 최댓값보다 작아질 때의 cnt를 반환한다.

코드

n = int(input())

cnt = 1
# 2번째 줄의 최댓값
max_range = 1 + (6 * cnt)

if n == 1:
    print(cnt)
else:
    cnt += 1
    while n > max_range:
        max_range += (6 * cnt)
        cnt += 1
    print(cnt)

특기 사항

수학적 능력이 좋으신 분들은 나처럼 길게 짤 것 없이 간단히 공식을 유도해냈다.

n = int(input())
x = ((n-1)/3)**(1/2)
print(round(x)+1)

평생을 수포로 살다가 지금 와서 갑자기 수학 능력을 높이는 거야 말도 안 되지만, 아쉽게 느껴지기는 하네.