[백준] 2292 벌집

백준의 해당 문제는 링크를 통해 들어가서 풀어볼 수 있다.

 

https://www.acmicpc.net/problem/2292

 

문제

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

입력

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

출력

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

정답

n = int(input())

room = 1 # 현재 방 개수
layer = 1 # 층수

while n > room:
    room += 6*layer
    layer += 1
    
print(layer)

공부한 내용

이 문제도 앞서 풀었던 중앙 이동 알고리즘 문제와 같이 패턴을 찾아야 하는 문제였다. 문제에서 그림과 같이 육각형 도형에서 1이 중심이라고 생각했을 때, 1과 바로 인접해 있는 6개의 숫자들과 그 다음 인접해 있는 6개의 숫자들 ... 간의 규칙을 찾아야 했다.

 

벌집은 이렇게 구성됩니다:

• 1층 : 1개 (1번 방)
• 2층 : 1 + 6 = 7번까지
• 3층 : 1 + 6 + 12 = 19번까지
• 4층 : 1 + 6 + 12 + 18 = 37번까지

여기서 규칙은 2층에서 6을 더하고, 3층에서는 12를 더하고, 4층에서는 18을 더하고 ..

발견했나요 ?

바로 6의 배수가 계속 더해지면서 층별 구성되어지는 방들의 숫자가 일정하게 증가하고 있었다.

 

따라서, 위의 코드와 같이 "현재 방"과 "층수"를 각각 1로 설정한 뒤, while 반복문을 사용해서 입력되어지는 방의 숫자, n이 현재위치인 1보다 크다면, room은 그 다음 층의 최대 방의 숫자인 7로 넘어가게 되는 동시에 층 수도 1이 증가하여 2가 된다. 여기서 또 n이 현재 방인 7보다 크다면, 다음 층에 있는 방이니까 room과 layer의 변수의 값이 반복해서 증가하게 된다.