백준알고리즘 2292번 : 벌집 [파이썬]

2021. 4. 13. 16:06

문제

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

 

 


입력

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


출력

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


해설

2292번 벌집 문제는 규칙을 찾으면 쉽게 풀 수 있는 문제이다.  여기서 필자가 설명을 편하게 하기 위해 아래 그림에서 주황, 파랑, 노란색, 초록색, 빨간색의 육각형을 방의 집합이라고 표현하겠다.  여기서 방의 집합은 각 단계를 가지고 있다고 표현하겠다. (예 : 주황 1단계, 파란색 2단계, 노란색 3단계) 그리고 1, 2, 3, 4, 5 와 같이 각 숫자를 방이라고 표현하겠다.

첫 번째 규칙은 각 방의 집합은 단계가 올라 갈수록 가지고 있는 방의 개수가 6개씩 증가한다. (첫 번째 제외) 

두 번째 규칙은 각 방의 집합에서 가장 큰 숫자는 이전 단계의 방의 집합들이 가지고 있는 총 방의 개수와 현재 단계의 방의 계수를 더하면 된다.

이러한 규칙을 이용하면 입력 숫자가 주어졌을 때 어떤 방의 집합에 속해있는지 찾아 출력할 수 있다.

 

 


코드

입력 숫자 N이 1이면 1을 출력한다.  만약 1이 아니라면 반복문을 이용하여 N보다 val가 커질 때 까지 두 번째 규칙을 이용하여 반복한다. 이때 tmp에 방의 단계를 저장한다. 조건이 만족하면 반복문을 멈추고 저장된 방의 단계를 출력한다. 

N = int(input())
tmp = 1
val = 1
tmpval = 0
tmpval2 = 0

if N == 1 :
    print(1)
else:
    while True :
        tmpval += 6
        val = val + tmpval
        tmp += 1
        if(val >= N):
            break
    print(tmp)