[백준] 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)가 주어진다.
첫째 줄에 분수를 출력한다.

입력	출력
1	1/1
2	1/2

---

✔️풀이

n=int(input())
cnt = 0
i = 0
while cnt<n:
  i += 1
  if cnt+i>=n:
    break
  cnt += i

idx = n-cnt
sum = i+1
if sum%2!=0:
  print(str(idx)+'/'+str(sum-idx))
else:
  print(str(sum-idx)+'/'+str(idx))

먼저 규칙을 찾았다.
지그재그의 한 방향에 있는 분수들의 공통점으로 분자와 분모의 합을 생각했다.
1/1 → (1/2 → 2/1) → (3/1 → 2/2 → 1/3) →
분자와 분모의 합이 2부터 1씩 커지며 각 합에 해당하는 분수의 개수도 1씩 커진다.

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

cnt는 분수의 총 개수, i는 지그재그를 하면서 늘어나는 분수의 개수를 의미한다.

while cnt<n:
  i += 1
  if cnt+i>=n:
    break
  cnt += i

분수의 총 개수가 n을 넘지 않을 때까지 계속해서 더해준다.
반복문에서 빠져나오면,
cnt의 값은 n번째 분수가 해당하는 대각선을 지나기 전 분수의 총 개수를 나타내고, i의 값은 각 대각선에 있는 분수들의 개수로 분자와 분모의 합보다 1 작은 값을 나타낸다.

idx = n-cnt
sum = i+1
if sum%2!=0:
  print(str(idx)+'/'+str(sum-idx))
else:
  print(str(sum-idx)+'/'+str(idx))

따라서 우리가 원하는 분수의 순서가 다음 대각선에서 몇번째인지 idx에 대입하고, 분자와 분모의 합을 찾는다.
합이 2의 배수일 때와 아닐 때의 지그재그 방향이 오른쪽 위에서 왼쪽 아래 또는 왼쪽 아래에서 오른쪽 위로 달라지기 때문에 if문을 사용해 해당 분수를 출력한다.