[Baekjoon] 1193번 분수찾기 S5 <Short>

1193번 - 분수찾기

1. 문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

• Input

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

• Output

첫째 줄에 분수를 출력한다.

2. 사용 알고리즘

• 수학 (Math)

3. 풀이

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

3.1. 수 나열

입력값 $x$ 와 이에 대한 출력값을 나열하면 다음과 같다.

 1 - 1/1   2 - 1/2   3 - 2/1   4 - 3/1
 5 - 2/2   6 - 1/3   7 - 1/4   8 - 2/3
 9 - 3/2  10 - 4/1  11 - 5/1  12 - 4/2
13 - 3/3  14 - 2/4  15 - 1/5  16 - 1/6
                  ⋮

3.2. 규칙 찾기

다음은 위에 나열된 분수를 분자와 분모 부분으로 구분하여 나타낸 표이다.

$x$	분자	분모
$1$	$1$	$1$
$2$	$1$	$2$
$3$	$2$	$1$
$4$	$3$	$1$
$5$	$2$	$2$
$6$	$1$	$3$
$7$	$1$	$4$
$8$	$2$	$3$
$9$	$3$	$2$
$10$	$4$	$1$
$11$	$5$	$1$
$12$	$4$	$2$
⋮	⋮	⋮

위 표에서 규칙성 있게 반복되는 구간별로 색상을 구분해 놓았다.

$x$ 에 대한 분자 결과값의 함수를 $n(x)$, 분모 결과값의 함수를 $d(x)$ 라고 두고 이 두 함수를 구해보자.

3.3. 보조함수 $f(x)$

$x$	$n(x)$	$d(x)$	$f(x)$
$1$	$1$	$1$	$1$
$2$	$1$	$2$	$2$
$3$	$2$	$1$	$2$
$4$	$3$	$1$	$3$
$5$	$2$	$2$	$3$
$6$	$1$	$3$	$3$
$7$	$1$	$4$	$4$
$8$	$2$	$3$	$4$
$9$	$3$	$2$	$4$
$10$	$4$	$1$	$4$
$11$	$5$	$1$	$5$
$12$	$4$	$2$	$5$
⋮	⋮	⋮	⋮

위 표에 표시된 값을 도출하는 함수 $f(x)$ 를 정의한다.

3.4. 보조보조함수 $g(x)$

함수 $f(x)$ 는 불연속함수 이므로, 이 함수를 도출가능한 연속함수 $g(x)$ 함수를 우선으로 찾아야 한다.

위 표에서 함수 $f(x)$ 의 함숫값 중 같은 함숫값에 대한 $x$ 의 최솟값만을 취하여 다시 표를 재작성하면 다음과 같다.

$x$	$f(x)$	$g(x)$
$1$	$1$	$1$
$2$	$2$	$2$
$4$	$3$	$3$
$7$	$4$	$4$
$11$	$5$	$5$
⋮	⋮	⋮

위 점들을 지나면서 연속함수인 $g(x)$ 를 구해야 한다.

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

위 표는 다음과 같이 일반화 할 수 있다.

$x$	$Δx$	$g(x)$
$1$		$1$
$2$	$1$	$2$
$4$	$2$	$3$
$7$	$3$	$4$
$11$	$4$	$5$
⋮	⋮	⋮
$g^{-1}(y)$	$y-1$	$y$

$$
g^{-1}(y) = 1 + \sum _{i=1} ^{y-1} i \
= 1 + {y (y - 1) \over 2} \
= {1 \over 2}y^2 - {1 \over 2}y + 1 \
= {1 \over 8} (2x - 1)^2 + {7 \over 8}
$$

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

$$ g(x) = {\sqrt{8x - 7} + 1 \over 2} $$

3.6. 숏코딩

더 효과적인 숏코딩을 위해 발악해보자.

3.6.1. 함수 $h(x)$ 찾기 ($g(x)$ 의 평행이동 함수)

좀 더 단순화된 함수를 찾기 위해 $g(x)$ 를 평행이동 하고자 한다.

제곱근 내부의 식을 간소화 하기 위해 $x$ 축 방향으로 $-{7 \over 8}$ 만큼 평행이동한 함수 $h(x)$ 는 다음과 같다.

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

$x$	$g(x)$	$h(x)$	$\text{floor}(h(x))$
$1$	$1$	$1.91$	$1$
$2$	$2$	$2.50$	$2$
$3$	$2.56$	$2.95$	$2$
$4$	$3$	$3.33$	$3$
$5$	$3.37$	$3.66$	$3$
$6$	$3.70$	$3.96$	$3$
$7$	$4$	$4.24$	$4$
$8$	$4.27$	$4.50$	$4$
$9$	$4.53$	$4.74$	$4$
$10$	$4.77$	$4.97$	$4$
$11$	$5$	$5.19$	$5$
$12$	$5.22$	$5.40$	$5$
⋮	⋮	⋮	⋮

위 표와 같이

$$
\left\lfloor g(x) \right\rfloor = \left\lfloor h(x) \right\rfloor
$$

를 만족함을 알 수 있다.

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

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

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

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

3.7. 함수 $n(x)$, $d(x)$

함수 $f(x)$ 를 통해 함수 $n(x)$, $d(x)$ 를 구할 수 있다.

임의의 변수 $a$, $t$, $b$ 에 대해 다음과 같이 정의한다.

$$ \begin{cases} a = f(x) \\ t = \sum _{n=1} ^{a} {(n-1)} \\ b = x - t \\ \end{cases} $$

이를 아래 표와 같이 나타낼 수 있다.

$x$	$a$	$t$	$b$	$a - b + 1$
$1$	$1$	$0$	$1$	$1$
$2$	$2$	$1$	$1$	$2$
$3$	$2$	$1$	$2$	$1$
$4$	$3$	$3$	$1$	$3$
$5$	$3$	$3$	$2$	$2$
$6$	$3$	$3$	$3$	$1$
$7$	$4$	$6$	$1$	$4$
$8$	$4$	$6$	$2$	$3$
$9$	$4$	$6$	$3$	$2$
$10$	$4$	$6$	$4$	$1$
$11$	$5$	$10$	$1$	$5$
$12$	$5$	$10$	$2$	$4$
⋮	⋮	⋮	⋮	⋮

따라서 함수 $n(x)$, $d(x)$ 는 다음과 같다.

$$ a = \left\lfloor \sqrt{2x} \right\rceil $$

$$ b = x - \sum_{n=1}^{a} \frac{n(n-1)}{2} $$

$$ n(x) = \begin{cases} b, & \text{if } a \ \% \ 2 = 0 \\ a - b + 1, & \text{if } a \ \% \ 2 = 1 \end{cases} $$

$$ d(x) = \begin{cases} a - b + 1, & \text{if } a \ \% \ 2 = 0 \\ b, & \text{if } a \ \% \ 2 = 1 \end{cases} $$

4. 제출 코드

위 알고리즘으로 코드를 작성하면 다음과 같다.

맞았습니다!!

n=int(input())*2;a=round(n**.5);b=(n-a**2+a)/2;print('%d/%d'%(a-b+1,b)[::a%2*2-1])