[BAEKJOON] 백준 1193번: 분수찾기 (Python)

문제 링크: https://www.acmicpc.net/problem/1193

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)가 주어진다.

---

코드

X = int(input())
cnt = 1

while X > int(cnt*(cnt+1)/2):
    cnt += 1
    
location = X - cnt*(cnt-1)/2

num1 = str(int(location))
num2 = str(int(cnt - location + 1))

if cnt%2 ==0:
    print(num1+"/"+num2)
else:
    print(num2+'/'+num1)

코드 설명

1. 수열이 그림과 같이 진행될 때, 숫자 X가 주어졌을 때, X번째 분수를 구하는 문제이다.
2. 수열의 흐름을 파악하기위해 그림을 표를 살펴보면, 대각선을 기준으로 line을 나눌 때, 홀수 번째는 하향으로, 짝수 번째는 상향하는 모양이다.
3. x축을 기준으로 첫 번째 라인은 대각선이 몇 번째 대각선인지 알 수 있다.(1/1 -> 1번째, 1/2 -> 2번째, 1/3 -> 3번째, ...)
4. 대각선의 숫자는 대각선 라인 내 존재하는 원소의 개수와 동일하다.
5. 숫자 X가 주어지고, 대각선의 숫자를 더할 때 X보다 큰 cnt 대각선 라인에 X는 존재한다.
   

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

6. 대각선 cnt에서 숫자 X가 몇 번째에 위치하는지 파악하기 위해 현재 대각선 라인 이전(cnt-1) 까지의 대각선 라인 숫자를 모두 더해주고 숫자 X를 뺀다.
   

   location = X - cnt*(cnt-1)/2​

7. 대각선 라인 내 몇 번 째 위치하는지 알았으므로, 분모, 분자가 1씩 변화하는 규칙을 이용하여 해당 X번째 분수를 찾는다.
   

   num1 = str(int(location))
   num2 = str(int(cnt - location + 1))​

   (분모와 분자의 합은 cnt + 1이다. 이를 활용하여 분자 또는 분모가 location일 경우, 분모 또는 분자는 cnt - location +1이 된다.)
8. 대각선이 홀수 번째, 짝수 번째인지 구분하여 결과를 출력한다.
   

   if cnt%2 ==0:             # 짝수번째 라인일 경우
       print(num1+"/"+num2)
   else:					  # 홀수 번째 라인일 경우
       print(num2+'/'+num1)​