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])
'Computer Science > Baekjoon' 카테고리의 다른 글
[Baekjoon] 10101번 삼각형 외우기 B4 <Short> (1) | 2024.01.20 |
---|---|
[Baekjoon] 1068번 트리 G5 (0) | 2024.01.15 |
[Baekjoon] 2839번 설탕 배달 B1 <Short> (0) | 2023.11.12 |
[Baekjoon] 2292번 벌집 B2 <Short> (0) | 2023.10.22 |
[Baekjoon] 2096번 내려가기 G5 (0) | 2023.09.23 |