[백준/Python] 1193 - 분수 찾기

문제

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

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	1/2
3	2/1
4	3/1
5	2/2
6	1/3
7	1/4
8	2/3
9	3/2
14	2/4

---

풀이

설계

1. 분수를 각 줄별로 배열하면 다음과 같은 규칙을 찾을 수 있다.
   짝수 번째 줄의 경우 분자가 증가하고 분모가 감소한다.
   홀수 번째 줄의 경우 분모가 증가하고 분자가 감소한다.
   예를 들면 다음과 같다.

   • 2번째 줄
     2 = (1+0) / (2-0) = 1/2
     3 = (1+1) / (2-1) = 2/1
   • 3번째 줄
     4 = (3-0) / (1+0) = 3/1
     5 = (3-1) / (1+1) = 2/2
     6 = (3-2) / (1+2) = 1/3
   • 4번째 줄
     7 = (1+0) / (4-0) = 1/4
     8 = (1+1) / (4-1) = 2/3
     9 = (1+2) / (4-2) = 3/2
     10 = (1+3) / (4-3) = 4/1
   • 5번쨰 줄
     11 = (5-0) / (1+0) = 5/1
     12 = (5-1) / (1+1) = 4/2
     13 = (5-2) / (1+2) = 3/3
     14 = (5-3) / (1+3) = 2/4
     15 = (5-4) / (1+4) = 1/5

2. x번째 분수가 몇 번째 줄에 속하는지를 파악한다.
   x에서 i(1, 2, 3...)순으로 빼면서 x가 i보다 커지면 x는 i번째 줄에 위치하게 된다.
   그리고 이때 x에서 순차적으로 i를 제하고 남은 x가 i번째 줄에서의 순서가 된다.
   예를 들면 다음과 같다.

   • 5 = 5, 1 → 4, 2 → 2, 3 = 3번째 줄의 2번째
   • 8 = 8, 1 → 7, 2 → 5, 3 → 2, 4 = 4번째 줄의 2번째
   • 14 = 14, 1 → 13, 2 → 11, 3 → 8, 4 → 4, 5 = 5번째 줄의 4번째

3. i의 홀짝에 따라 규칙을 적용한다.
   i가 짝인 경우 분자는 1+(x-1), 분모는 i-(x-1)이 된다.
   i가 홀인 경우 분자는 i-(x-1), 분모는 1+(x-1)이 된다.

코드

x = int(input())
i = 1

# x가 몇 번째 줄에 속하는지 확인
while x > i:
    x -= i
    i += 1

# 짝수에 대한 규칙 적용
if i % 2 == 0:
    print(f"{1+(x-1)}/{i-(x-1)}")
# 홀수에 대한 규칙 적용
else:
    print(f"{i-(x-1)}/{1+(x-1)}")