[백준] 2292번 벌집(python)

문제소개

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

입력

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

출력

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

풀이과정

이문제를 처음 접근할때 많은 고민이 있었다.
그러다 문득 벌집을 껍질로 접근해서 N이 몇번째 껍질에 있는지 알면 풀 수 있을 거 같은 직감이 왔다.

벌집은 층층이 갯수가 늘어나면서 그 전의 벌집을 둘러싸는 형태이기때문에 이를 '껍질'로 지칭하겠습니다. 예를 들어 1번방은 1껍질, 2-7번방은 2껍질, 8-19는 3껍질입니다.

이 후엔 N번 방이 있는 껍질의 번호가 1부터의 최단 거리라는 것을 알게 되었다.

예를 들어 13번 방은 1번 방으로부터 일직선으로 위치해있고 3번 껍질에 위치하므로 3개의 방을 지나치면 도착한다.
또한 14번 방은 13번 방과 동일한 3번 껍질에 위치해 있지만 1번 방으로부터 일직선에 위치하고 있지 않다. 하지만 그 전 껍질의 방(4번방)에서 방향만 바꾸어 이동하면 14번방에 도착할 수 있다.

즉 N번방이 위치하는 껍질 번호가 1부터 N번방까지 지날 때 지나는 최소의 방 갯 수이다.

우선 각 껍질의 방 갯수에서 규칙을 찾아 보기로 했습니다.

• 1번 껍질은 1개의 방 (1번방)
• 2번 껍질은 6개의 방 (2-7번방)
• 3번 껍질은 12개의 방 (8-19번방)
• 4번 껍질은 18개의 방 (20-37번방)

2번 껍질부터 각 껍질의 방 갯수가 6씩 증가하는 걸 발견했습니다.

문제는 N번 방이 몇 번 껍질에 위치하는지를 알면 풀리기에
i번째 껍질까지의 방 개수를 등차수열을 합 공식을 써서 구했습니다.
(공차는 6, 첫째 항은 6, 1번방은 포함이 안되므로 1을 더해야 함)

$S =$ $i(2a+(i-1)d)\over 2$$+1$


$S =$ $i(12+(i-1)6)\over 2$$+1$


$S =$ $6i^2+6i\over 2$$+1$


$S =$ $3i^2+3i+1$

시작항이 6이므로 위 공식은 i+1번껍질의 방 갯수이다.
이를 i번 껍질의 방 갯수로 바꾸기 위해 i자리에 i-1을 대입했다.
그래서 최종 공식은 아래와 같다

$S =$ $3(i-1)^2+3(i-1)+1$

문제에서 주어진 N번 방이 몇 번째 껍질에 있는지를 알면 되기 때문에 나는 while문을 이용해 i값을 하나씩 늘려가면서 총 합이 N번의 번호보다 크거나 같으면
그 i값이 N번 방이 위치하고 있는 껍질이므로 이를 출력한다.

전체코드

n = int(input())
i = 1
while n:
    
    if 3*(i-1)**2 + 3*(i-1) + 1 >= n:
        break

    i += 1

print(i)

수학적 사고를 연습하기에 좋은 문제였던거 같다. 복잡해 보이는 문제가 있으면 혹시 규칙이 있지 않는지 생각해봐야 겠다.