[백준 2292] 벌집 / 파이썬

시간제한 : 2초

메모리제한 : 128MB

문제 :

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

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

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

---

풀이

N번째 방을 가기 위해 지나가야 하는 방의 숫자는 그 방이 속한 테두리의 수열로 구할 수 있다.

가령, 두 번째 육각형에 속한 7번 방까지 가기 위해 지나가야 하는 방의 숫자는 2, 네 번째 육각형에 속한 24번 방까지 지나가기 위해 지나가야 하는 방의 숫자는 4이다. 

 

n번째 육각형에 포함되는 방의 숫자는

n=1일때 1, n=2일때 7(1 + 6), n=3일때 19(1+6+12), n=4일때 37(1+6+12+18)...로,

수열 a(n)은 n이 1일 때, a(n)=1, n이 2 이상일 때는 6 * 2(n-1)인 수열의 합으로 표현할 수 있다.

 

따라서 a(n)은 3 n(n-1)+1이 된다.

 

이제 주어진 방의 번호 N이 n번째 육각형에 속한 방의 번호보다 작아질 때까지 while 반복문을 돌린 후, while 반복문이 멈췄을 때의 n 값을 출력하면 값을 구할 수 있다.

N = int(input())

n = 1
rooms = 1

while N > steps:
    n += 1
    rooms = 1 + 3 * n * (n-1)
print(n)