백준 2292번 벌집문제 - Python

문제

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

입력

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

출력

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

예제 입력 

13

예제 출력 

3

 

이 문제를 푸는데 있어서 수학적으로 해결하고자 여러 시도를 해봤습니다. 여러번 끄적이면서 수의 규칙을 찾아냈습니다

1 => 1

2 => 2~7,   // 6개 

3 =>  8~19 // 12개 

4 =>  20~37 // 18개 

5 =>  38~61 // 24개

이 형태가 나오는 것을 보고서 등차계차수열임을 알게 되었습니다. 하지만.. 고등학교 교육과정을 잊은지 오래 되었기 때문에 풀기 위해서는 다시 공식을 참고하면서 수식을 도출해내야 했습니다.

이렇게 일반식을 만들게 되면 n이 1일때부터 위 문제에 대하여 모든 해결이 가능합니다.

식이 도출되었다면 푸는 것은 매우 쉽습니다

내가 입력한 수가 위 공식대로 n=1 부터 차례로 늘려가면서 계속 반복문을 돌고 입력한 값보다 커진 n번째에서 빠져나와서 n을 출력하게 되면 그것이 벌집의 1에서 최소의 거리가 됩니다.

이 문제는 아래 문제 테마가 수학인것을 고려해보면 위와 같이 공식을 도출해서 문제를 해결하는 것이 출제의도로 생각됩니다

N = int(input())
n = 1


while 1+3*(n)*(n-1) < N:
    n+=1

print(n)