[BOJ 1193번] 분수찾기(Python)

📝 문제

💡 무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
이와 같이 나열된 분수들을
1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로
차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

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

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

 

문제링크

1193번: 분수찾기

---

✅ 풀이

n = int(input())
i = 0
sum = 0

while True:
    i += 1
    if sum + i >= n:
        break
    sum += i

left = n - sum
hap = i+1
head = hap - left

if hap % 2:
    print("%d/%d" % (left, head))
else:
    print("%d/%d" % (head, left))

💡 같은 대각선 라인에 위치한 분수들의 분자, 분모 합이 같은 것을 이용했다.
1/1을 시작으로 대각선 별로 원소의 수가 1,2,3....과 같이 증가하기 때문에,
찾으려는 번호의 분수가 위치한 대각선 라인의 분자, 분모 합을 먼저 찾았다.

이 때 분자, 분모의 합이 짝수인 경우, 분모가 오름차순으로 진행되고
홀수인 경우, 분자가 오름차순으로 진행되기 때문에,
위의 규칙을 이용해서 원하는 위치의 분수를 찾아주었다.