[Baekjoon] 2292번 벌집 B2 <Short>

2292번 - 벌집

1. 문제

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

• Input

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

• Output

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

2. 사용 알고리즘

• 수학 (Math)

3. 풀이

해당 풀이는 가능한 한 코드의 길이를 줄이고자 하는 숏코딩 방식으로 구현되었다.

3.1. 수 나열

번호와 그 번호 방까지 지나는 최소 방 개수를 짝지으면 다음과 같다.

 1 - 1   2 - 2   3 - 2   4 - 2
 5 - 2   6 - 2   7 - 2   8 - 3
 9 - 3  10 - 3  11 - 3  12 - 3
13 - 3  14 - 3  15 - 3  16 - 3
17 - 3  18 - 3  19 - 3  20 - 4
              ⋮

3.2. 문제의 확장

이는 곧,

x - y

$$y=f(x)$$

를 만족하는 함수 $f(x)$ 를 구하는 문제로 확장된다.

3.3. 규칙 찾기

함수 $f(x)$ 는 불연속함수이며, 연속함수로부터 도출될 수 있는지 생각해볼 수 있다.

$x \gt 1$ 인 경우 중, 하나의 함숫값으로 대응되는 여러 $x$ 값들 중 최솟값만을 표시하면 다음과 같다.

 2 - 2   8 - 3  20 - 4  38 - 5
              ⋮

위 점들을 지나는 연속함수 $g(x)$ 가 있다고 할 때, 이 함수를 통해 함수 $f(x)$ 를 역추론 할 수 있다.

함수 $g(x)$ 의 자연수 $x$ 에 대한 함숫값 $y$ 쌍을 나타내면 다음과 같아질 것이다.

           2 - 2.0   3 - 2.X   4 - 2.X
 5 - 2.X   6 - 2.X   7 - 2.X   8 - 3.0
 9 - 3.X  10 - 3.X  11 - 3.X  12 - 3.X
13 - 3.X  14 - 3.X  15 - 3.X  16 - 3.X
17 - 3.X  18 - 3.X  19 - 3.X  20 - 4.0
                  ⋮

함수 $g(x)$ 는 점 $(2, 2)$, $(8, 3)$, $(20, 4)$ ... 등을 지나며 우상향 그래프라는 것을 추측할 수 있다.

3.4. 함수 $g(x)$ 찾기

함수 $g(x)$ 는 다음의 점들을 지난다.

 2 - 2   8 - 3  20 - 4  38 - 5
              ⋮

위 쌍을 일반화 해보자.

$x$	$Δx$	$ΔΔx$	$y$	$Δy$
$2$			$2$
$8$	$6$		$3$	$1$
$20$	$12$	$6$	$4$	$1$
$38$	$18$	$6$	$5$	$1$
⋮	⋮	⋮	⋮	⋮
$g^{-1}(y)$	$6(y-2)$	$6$	$y$	$1$

$$
g^{-1}(y) = 2 + \sum _{i=3} ^{y} 6(i-2) \
= 2 + 6 \cdot {(y - 1) (y - 2) \over 2} \
= 3y^2 -9y + 8 \
= 3 \left( y - {3 \over 2} \right) ^2 + {5 \over 4}
$$

따라서 함수 $g(x)$ 는 다음과 같다.

$$ g(x) = \sqrt{ {1 \over 3} \left(x - {5 \over 4} \right) } + {3 \over 2} $$

            2 - 2.00   3 - 2.26   4 - 2.46
 5 - 2.62   6 - 2.76   7 - 2.88   8 - 3.00
 9 - 3.11  10 - 3.21  11 - 3.30  12 - 3.39
13 - 3.48  14 - 3.56  15 - 3.64  16 - 3.72
17 - 3.79  18 - 3.86  19 - 3.93  20 - 4.00
                    ⋮

3.5. 함수 $g(x)$ 의 한계

다만, 함수 $g(x)$ 는 정의역이

$$ \Bigl\{ x | x \ge {5 \over 4} \Bigr\} $$

이므로 $x = 1$ 에서 함숫값이 정의되지 않는다.

$g(x)$ 를 평행이동한 함수 $h(x)$ 를 새로 정의하면 다음과 같다.

$$h(x) = g\left(x + {1 \over 4} \right) = \sqrt{ {x - 1 \over 3} } + {3 \over 2} $$

3.6. 함수 $f(x)$ 찾기

새로 정의한 함수 $h(x)$ 는 점 $(2, 2)$, $(8, 3)$, $(20, 4)$ ... 등을 지나지 않지만,
자연수 $x$ 에 대한 함숫값 $y$ 쌍을 나타내면 다음과 같다.

 1 - 1.50   2 - 2.08   3 - 2.32   4 - 2.50
 5 - 2.65   6 - 2.79   7 - 2.91   8 - 3.03
 9 - 3.13  10 - 3.23  11 - 3.33  12 - 3.41
13 - 3.50  14 - 3.58  15 - 3.66  16 - 3.74
17 - 3.81  18 - 3.88  19 - 3.95  20 - 4.02
                    ⋮

여기서 함숫값을 내림하면

 1 - 1   2 - 2   3 - 2   4 - 2
 5 - 2   6 - 2   7 - 2   8 - 3
 9 - 3  10 - 3  11 - 3  12 - 3
13 - 3  14 - 3  15 - 3  16 - 3
17 - 3  18 - 3  19 - 3  20 - 4
              ⋮

위와 같아지며, 함수 $f(x)$ 와 동일하다.

따라서 함수 $f(x)$ 는 다음과 같다.

$$ f(x) = \lfloor h(x) \rfloor = \left\lfloor \sqrt{ {x - 1 \over 3} } + {3 \over 2} \right\rfloor $$

$ \left\lfloor x + {1 \over 2} \right\rfloor = \lfloor x \rceil $

더 짧은 코드를 위해 위의 개념을 사용하였다.

따라서 함수 $f(x)$ 는 최종적으로 다음과 같다.

$$
f(x) = \left\lfloor \sqrt{ {x - 1 \over 3} } + 1 \right\rceil \
= \left\lfloor \sqrt{ {x - 1 \over 3} } \right\rceil + 1
$$

4. 제출 코드

맞았습니다!!

print(1+round(((int(input())-1)/3)**.5))