2292번(벌집) 파이썬(Python) 풀이 공유

들어가며

나를 알 수 없는 늪으로 빠지게 한 문제이다. 문과 출신이라 그런지 수학이랑 그다지 친하지는 않은데도 불구하고 가우스 공식을 코딩에 접한 이후로 공식 만드는 재미에 빠져서 공식을 세우기 위해 약 한 시간 가량을 삽질했지만, 결국에는 whlie 문으로 해결하였다.

1. 문제

• 2292번 벌집

시간 제한	메모리 제한
2 초	128 MB

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

1.1. 입력

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

1.2. 출력

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

1.3. 예제

입력	출력
13	3

2. 풀이

먼저 1을 중심으로 둘러싼 육각형들의 집합을 둘레층이라고 해보자. 각 둘레층에는 값의 범위와 최댓값이 존재하는데, 이들을 아래 표와 같이 정리해보면 값의 범위 중 최댓값은 이전 최댓값에서 6의 배수만큼 증가한다는 규칙을 발견할 수 있다.

둘레층	최댓값	값의 범위	규칙
1	1	1	해당없음
2	7	2 ~ 7	1 + (6 × 1)
3	19	8 ~ 19	7 + (6 × 2)
4	37	20 ~ 37	19 + (6 × 3)

위의 규칙을 적용하여 while 문으로 구현하면 쉽게 문제를 해결할 수 있다.

N = int(input())
level = 1

if N > 1:
    max_number = 1

    while N > max_number:
        max_number += 6*(level)
        level += 1

print(level)

• Line 1 : 변수 N을 입력받은 값으로 초기화한다.
• Line 2 : 1이 위치하는 방의 개수도 포함하므로 둘레층을 나타내는 변수 level을 1로 초기화한다.
• Line 4 - 5 : N이 1인 경우에는 규칙을 적용하지 않으므로, N이 1보다 큰 경우에만 반복문을 수행하고, 반복문을 수행하며 둘레층의 최댓값을 알아내기 위해 최대값 변수 max_number를 1로 초기화한다.
• Line 7 : N이 최댓값보다 작아야 해당 둘레층에 위치하는 것이므로, N이 최댓값보다 큰 경우에 while 문을 종료한다는 조건을 설정하여 반복을 수행한다.
• Line 8 - 9 : 각 반복마다 최대값은 6의 배수만큼, 둘레층은 1 만큼 증가시킨다.
• Line 11 : 최종적으로 측정한 둘레층을 출력한다.

마치며

알고리즘의 성능을 위해 반복문을 최대한 덜 쓰는게 좋긴 하지만, 때로는 너무 복잡한 생각이 스스로를 알 수 없는 늪으로 빠지게 하는 것 같다. 공식을 적용해서 코드의 성능을 높이려는 욕심은 잠시 접어두고 논리적으로 문제를 먼저 해결하는 게 우선임을 다시 한 번 되새긴다.