테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 벌집 ======

===== 풀이 =====
  * 간단한 수학문제
  * 거리가 1인 칸이 1개인것만 제외하면, 거리가 2인 칸은 6개, 3인 칸은 12개, 4인 칸은 18개.. 이렇게 거리가 x인 칸의 갯수는 6(n-1)개이다.
  * 그래서 거리가 x이하인 칸의 갯수는 1 + sigma(6*(i-1)) = 1 + 3*x*(x-1) 개.
  * 결국 풀이는 1+3*x*(x-1) 가 n이상이 되는 가장 작은 x를 찾으면 된다. 
  * 그냥 x를 1부터 증가시키면서 계산해보는 O(sqrt(n)) 알고리즘으로도 충분히 풀리기는 한다.
  * 그러나 그냥 수식을 조금만 전개하면 계산식을 바로 구할수 있다. 1+3*x*(x-1) >= n > 1+3*(x-1)*(x-2) 에서 우측 부분을 정리하자
    * $n \geq 2+3(x-1)(x-2)$ 로 바꿔쓰고, 오른쪽을 완전제곱식형태로 만들면 $ \frac{(n-2)}{3} + \frac{1}{4} \geq (x-\frac{3}{2})^2$ 이 되므로 $x \leq \sqrt{\frac{(n-2)}{3} + \frac{1}{4}} + \frac{3}{2}$ 가 된다. 다시 정리하면 $x=\lfloor\frac{\sqrt{12n-15}+9}{6}\rfloor$. n이 1일때는 따로 처리해야 한다는 것만 신경쓰자.
  * 이렇게 계산하면 O(1)에 해결 가능.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2292. 벌집".

- Problem link: https://www.acmicpc.net/problem/2292
- Solution link: http://www.teferi.net/ps/problems/boj/2292
"""


def main():
    N = int(input())
    print('1' if N == 1 else int(((12 * N - 15)**0.5 + 9) / 6))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:브론즈_2}}