백준 알고리즘 - 2792 - 벌집

문제

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

---

입력

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

---

출력

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

 

---

접근법

수학 파트인 만큼 수학적으로 어떻게 접근하는지가 중요한 문제이다.

1을 중심으로 층별로 개수가 6, 12, 18, 24 개씩 벌집이 형성되어 있다.

각 층의 벌집 개수는 6의 배수만큼 증가한다.

 

1층 = 1

2층 = 2~7

3층 = 8~19

4층 = 20~37

5층 = 38 ~ 61

...

 

이를 수학적으로 표현하면

1층 = 1

2층 = 6 × 0 + 2 ~ 6 × 1 + 1

3층 = 6 × 1 + 2 ~ 6 × 3 + 1

4층 = 6 × 3 + 2 ~ 6 × 6 + 1

5층 = 6 × 6 + 2 ~ 6 × 10 + 1

...

 

곱해지는 수인 0, 1, 3, 6, 10은 등차수열이므로 등차수열 함수를 하나 만든 후

입력받은 n이 각 층에 해당되는 지를 확인하는 조건을 만든다.

n이 어떠한 층에 해당되면 return해 준다.

---

코드

def arithmetic(n): # 등차수열 함수
    answer = 0
    i = 1
    for _ in range(n):
        answer += i
        i += 1
    return answer

def bee():
    n = int(input())
    layer = 1 # 처음엔 1층부터 시작
    while True:
        if 6*arithmetic(layer-1)+2 <= n and n <= 6*arithmetic(layer)+1:
            return layer+1
        elif n == 1:
            return 1
        layer+=1

bee()

시간 초과가 나는 코드이다.

 

굳이 6의 배수만큼 더해주기 위해 등차수열 함수를 만들 필요가 없다.

 

그냥 n이 해당 층의 마지막 수보다 작다면 그 층을 print해주면 된다.

n = int(input())
first = 1
plus = 6
layer = 1

if n == 1:
    print(1)

else:
    while True:
        first = first + plus
        layer += 1
        if n <= first:
            print(layer)
            break
        plus += 6