[백준 1193] 분수찾기 / 파이썬

시간제한 : 0.5초

메모리제한 : 256MB
문제 :

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

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/1) -> (1/2 - 2/1) -> (3/1 -> 2/2 -> 1/3) ...

각 대각선에 포함된 숫자는 등차가 1인 등차 수열을 따른다. 1 -> 2 -> 3 -> 4 ...

 

또한 n번째 대각선에 속해 있는 분수에서 분자와 분모의 합은 n+1이며, 

홀수번째 대각선인 경우 n/1 -> n-1 / 2 -> n-2 /3 -> ... -> 1/n

짝수번째 대각선인 경우 1/n -> 2 / n-1 -> 3 / n-2 -> ... -> n/1

의 순서대로 분수가 정해진다. 

 

따라서 X번째에 해당하는 분수를 확인하기 위해서는

1) X가 몇 번째 대각선에 속하는지를 확인하고

2) 포함되는 대각선 안에서 몇 번째에 등장하는지를 알아내야 한다.

 

먼저 X가 속한 대각선의 위치는 수열 a(n) = n(n+1)/2보다 커지는 가장 작은 n값이 된다.

이렇게 n값을 구한 후, X에서 a(n-1)을 빼면, X가 n번째 대각선에서 등장하는 차례를 확인할 수 있다.

 

이때, n이 짝수인 경우와 홀수인 경우에 따라 분수가 등장하는 순서가 바뀌므로, 

이 조건을 조심하여 분수를 출력하면 된다. 

X = int(input())

cnt = 1
criteria = 1

while X > criteria:
    cnt += 1
    criteria  = cnt * (cnt + 1) * 1/2

cri2 = X - cnt * (cnt -1) * 1/2
if cnt % 2 == 0:
    print(f'{int(cri2)}/{int(cnt -cri2 + 1)}')
else:
    print(f'{int(cnt-cri2+1)}/{int(cri2)}')