백준 2292 - 벌집(파이썬)

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

2292번: 벌집

---

 

---

코드 

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번 방을 갈 때와 필요 개수가 동일함 그러므로 올림 처리를 해주면 됨!