백준 2292번, 벌집, Python3 [BOJ]

파이썬으로 풀었다.

 

오 제한 2초다.

문제

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

 

입력

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

 

출력

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

 

---

당연히 처음부터 잘 풀면 재미없지

 

import sys
num = int(sys.stdin.readline())
answer = 1
def f(a):
    return ((3*a**2)-(3*a)+1)

while num > answer:
    f(answer)
    if answer > num:
        print(answer-1)
        break
    answer += 1
    

 

바로 시간초과 떠버리고?

처음엔 6개의 변이 바깥쪽과 마주하고

다음에는 3개의 변이 바깥쪽과 마주하고 진행된다.

그 다음에는 2개의 변??

아 뭔가 아닌데

 

다시

한바퀴 돌았을 때 그 숫자를 잘 보자

1 7 19 37 61 ...?

흠.. 계차수열인가?

7-1 = 6 

19-7 = 12

37-19 = 18 

61-37 = 24 

규칙이 변하지 않았을 때 계차수열임을 발견.

 

적용 ㄱㄱ

하지만 좀 더 빠를만한 방식으로

 

정답

import sys
num = int(sys.stdin.readline())
n = 1
answer = 0
def f(a):
    return ((3*a**2)-(3*a)+1)

while num >= answer:
    answer = f(n)
    if answer >= num:
        print(n)
        break
    n += 1
    
    #계차수열임