백준 2292 - 벌집(파이썬)

https://www.acmicpc.net/problem/2292 해당 문제풀이입니다.

2292번: 벌집

---

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

시간제한	메모리제한	제출	정답	맞힌사람	정답 비율
2 초	128 MB	90899	40832	35147	44.852%

 

문제

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

입력

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

출력

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

예제 입력 1

13

예제 출력 1

3

 

 

---

코드 

import math
an = int(input())
#n테두리의 끝방번호는 계차수열 an= 1+3(n(n-1)) // {bn = 6n}
#일반항 3n^2 - 3n + 1-an = 0
#근의공식중 양수
#그사이에 해당하는 방은 전부 올림처리 
answer = math.ceil((3+(12*an -3)**(1/2))/6)
print(answer)

 

 

 

풀이

문제를 보니  1, 7, 19, 37, 61... 와 같이 계차수열을 이루면서 점점 거쳐가야 하는 방의 개수가 늘어남을 알 수 있었다.

여기서 계차 수열이란? 

계차수열은 수열의 인접한 두 항에 대하여, 뒤 항에서 앞 항을 뺀 값을 계차(階差 / difference)라고 하는데, 원래 수열의 계차들을 항으로 하는 수열이다. 따라서 계차수열은 그 자체로 성립하지 않고 별도로 원래 수열의 존재를 전제해야만 성립하는 개념이다.
출처 : 나무위키 https://namu.wiki/w/%EA%B3%84%EC%B0%A8%EC%88%98%EC%97%B4

계차 항수의 일반항은 이러한데

여기서 a1 = 1, 계차 Bk = 6n 이 된다!!

이를 이용해 An에 대한 일반항을 구해보면 An = 1 + 6(n*(n-1)/2)가 나온다. 

이식을 이용해 An값을 이용해 n값을 구하면 된다.

식을 정리해보면

3n^2 + 3n + 1-An = 0의 식이 나온다.

근의 공식

에 대입하여 우리는 n을 구하면 끝. (x=n , a=3 , b=3, c=1-An, An = 입력값)

그 후에 값들의 각 사이의 값들은 2~7번 방은 전부 7번 방을 갈 때와 필요 개수가 동일함 그러므로 올림 처리를 해주면 됨!