[백준][1193] 분수찾기

• Problem Link : https://www.acmicpc.net/problem/1193

문제

• 위 그림과 같이 큰 배열에 분수들이 적혀있다.
• 순서는 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → 1/3 ··· 과 같이 지그재그 순으로 진행된다.
• X가 주어질 때, X번째 분수를 구하여라.
  - 중요한 점은 지그재그의 진행방향이 바뀌므로 2가지 경우에 따라 분수를 따로 구해야한다는 것이다.

입력

• 첫째 줄, X가 주어진다.

출력

• X번째 분수를 출력한다.

—-

풀이

맨 왼쪽 행의 값들을 기준으로 삼아서 X번째가 몇번째 열로 끝나는 지를 알아본다. 이 때 첫번째 행의 순서 번호는 1, 3, 6, 10, 15 ··· 과 같는데 이는 n번째 열의 첫번째 행의 값 m(n)을 다음과 같이 정의 할 수 있다는 뜻이다.

따라서 X가 입력으로 주어진다면 $m(n) ⩽ X < m(n+1)$을 만족하는 n을 찾을 수 있다. 이를 만족하는 n을 구한 후 n이 짝수인지 홀수인지를 통해 지그재그의 진행 방향을 알 수 있고 따라서 다음과 같은 공식을 작성할 수 있다. X와 m(n), n을 이용해 다음과 같이 분수를 찾을 수 있다.

따라서 주어진 X값에 대하서 m(n)을 찾아 결과적으로 원하는 분수를 찾을 수 있다

코드

import sys

input = sys.stdin.readline

X = int(input())

n = 0
m = 0
while X > m:
    n += 1
    m = int(n * (n + 1) / 2)

if n % 2 == 0:
    numerator = n - (m - X)
    denominator = 1 + +(m - X)
else:
    numerator = 1 + (m - X)
    denominator = n - (m - X)

print(str(numerator) + "/" + str(denominator))