문제

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

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번째 분수를 구하는 프로그램을 작성하시오.

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

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

예제 입력 1
14

예제 출력 1
2/4

풀이 과정

X가 일정한 수 사이에 있을 때 분자나 분모에 올 수 있는 최댓값은 n이라고 정한다.
그 일정한 수는 a와 b라고 둔다.

반복을 하는데, X가 a 이상 b 이하이면 종료한다.
그렇지 않으면, a에 n을 누적하고 b에 n + 1을 누적한다.
n에 다시 1을 누적한다.

반복 종료 후, n이 홀수일 때,
분자는 n에서 X - a를 뺀 값이 되고,
분모는 X - a에서 1을 더한 값이 된다.

n이 짝수일 때,
분자와 분모의 값은 반대이다.

다른 방법으로, 해당 사선을 line으로 둔다.
line의 초깃값은 1이다.

X가 line보다 크면 반복한다.
X에 line만큼을 빼주고 line에는 1을 누적한다.

반복이 종료되면, 분자는 line에 X를 빼고 1을 더한 값이 된다.
분모는 X가 된다.
이 때, line 값이 짝수이면 분자와 분모의 값을 교환한다.

코드 1

X = int(input())
a = b = n = 1
top = bot = 0

while True:
    if a <= X <= b:
        break
    a += n
    b += n + 1
    n += 1

if n % 2 != 0:
    top = n - (X - a)
    bot = X - a + 1
else:
    top = X - a + 1
    bot = n - (X - a)

print(f'{top}/{bot}')

코드 2

X = int(input())
line = 1

while X > line:
    X -= line
    line += 1

top = line - X + 1
bot = X
if line % 2 == 0:
    top, bot = bot, top

print(f'{top}/{bot}')

백준 1193 분수찾기