[python] 백준 2292 : 벌집

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

2292번: 벌집

알고리즘 분류 : 수학

---

 

풀이 1 : 육각형 단위로 구분하기

 

그림을 중앙을 중심으로 하는 여러개의 육각형의 형태로 나누어 보자.

 

중심에 있는 육각형은 1,

그 다음으로 큰 육각형은 1~7까지,

그 다음으로 큰 육각형은 1~19까지,

그 다음은 1~37까지,

그 다음은 1~61까지의 숫자로 이루어져 있다.

 

이렇게 나누어진 범위를 활용하면 쉽게 문제를 풀 수 있다.

예를들어 13의 경우, 3번째 육각형의 범위에 해당하므로 1에서 13까지 가는데 지나가야 할 최소값은 3이다.

58의 경우, 5번째 육각형 범위에 해당하므로 최소값은 5다.

 

이 방법을 이용해 각 육각형의 범위를 코드로 구현해보자.

 

n번째 육각형 벌집의 개수 = n-1번째 육각형 벌집의 개수 + n번째 육각형 테두리의 벌집 개수

 

1번째 육각형의 개수 : 1

2번째 육각형의 개수 : 1+6

3번째 육각형의 개수 : 1+6+12

4번째 육각형의 개수 : 1+6+12+18

5번째 육각형의 개수 : 1+6+12+18+24

 

N = int(input())
sum = 1
count = 1
for i in range(N):
    sum = sum + 6*i
    if N > sum:
        count += 1
    else:
        break
print(count)

sum은 n-1번째 육각형 벌집의 개수를, 6*i는 n번째 육각형 테두리의 벌집 개수를 표현했다.

입력받은 숫자가 육각형의 범위를 벗어난 값이면 반복문을 벗어나도록 했다.

 

예시 :

N = 13입력

 

i = 0

sum = 1

N(13) > 1 -> count = 2

 

i = 1

sum = 1 + 6 = 7

N(13) > 7 -> count = 3

 

i = 2

sum = 1 + 6 + 12 = 19

N(13) > 19 -> break

count = 3 출력