[백준] 2292번 - 벌집

1. 문제

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

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

 

 

2. 코드

#1: 1(0) / 2: 6(6)(2~7) / 3 : 12(18)(8~19) / 4: 18(36)(20~37)

n = int(input())
cnt = 1
temp = 6

while n-1 > 0:
    n -= temp
    cnt += 1
    temp = temp + 6
    if n-1 <= 0:
        break;
    
print(cnt)

 

 

3. 알고리즘

: 첫번째는 1. 두번째는 2~7. 세번째는 8~19. 네번째는 20~37의 수이다.

가장 앞자리수(2, 8, 20, ...)만 봤을 때 6, 12, 18 등 6의 배수로 간격이 증가하는 것을 확인할 수 있다.

따라서 6의 배수만큼(temp)씩 차례대로 빼주면서 몇번째 구역(cnt)인지 센다.