2292

제목 : 벌집

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

• 입력 : 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
• 출력 : 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

중심에서 출발하여 인접한 방으로만 건너갈 때 최소 몇 개의 방을 옮겨가야 하는가? 하는 문제이다. 그림을 찬찬히 보면 알겠지만 첫 시작 위치를 기준으로 시계방향으로 방번호가 증가하며 ring 모양을 다 채우면 아래로 한칸 더 옮겨가야면서 새로운 ring을 만든다. 핵심은 ring에 해당하는 벌집의 갯수이다. 일단 내가 받은 N번의 벌집이 어느 ring에 위치하는가를 파악해야 최단거리를 알 수 있기 때문이다. 첫 위치(1번 방)을 제외하면 모든 ring은 6n개의 방으로 이루어져 있다. 게다가 애초에 초기위치가 인접한 6개의 방, 즉 전 방향으로 진행가능한 초기위치를 설정하고 있기 때문에 ring에 도착하는 것 자체가 최단거리와 동일하다. 그러므로 우리는 해당 ring만 찾아주면 된다.

코드는 다음과 같다.

import sys
n = int(sys.stdin.readline())

if n ==1:
    print(1)
else:
    i=0
    j=1
    while n>j:
        j+=6*i
        i += 1
    print(i)

코드를 보면 감이 올 텐데, 주어진 n이 1인 경우는 6n의 형태가 아니가 때문에 예외처리를 해주고, 나머지는 몇 개의 ring을 지나야 하는지만 확인해주면 된다. 문제에서 주어진 예시와 같이 13인 경우, 1(초기위치) + 6(첫 ring) < 13 < 1+6+12(두 번째 ring)이기 때문에 두 번째 ring 내에 위치하고 있음을 알 수 있다. 즉 초기위치+ring1+ring2=3이므로 정답은 3이 된다. 마찬가지로 58의 경우 1+6+12+18+24 < 58 < 1+6+12+18+24+36이기 때문에 5번 ring 내에 위치하고 있다는 것을 알 수 있어서 정답은 5가 된다.

코딩보다는… 수학문제 아닐까? 약간 모의고사 스타일;