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 = int(input())
n = 1

while X > (n*(n+1)/2):
    n += 1
    
d = int(n*(n+1)/2) - X

if n % 2 == 0:
    print('{}/{}'.format(n-d,1+d))
else:
    print('{}/{}'.format(1+d,n-d))

 

• 우선 나열된 분수들을 보면 대각선을 하나의 줄이라고 생각했을 때 같은 줄에 있는 분수끼리는 분모 분자의 합이 동일합니다. 이 점에 착안해서 다음과 같은 순서로 진행했습니다.
  1. 입력된 숫자가 몇 번째 줄에 있는 숫자인지 알아냅니다.
  2. 짝수 줄/홀수 줄이냐에 따라 가장 마지막 값이 n/1 인지, 1/n인지가 결정되므로 케이스를 나눠줍니다.
  3. 알아낸 줄의 가장 마지막 번째 값을 기준으로 입력된 숫자와 몇 번의 차이가 나는지를 계산해 최종 답을 구해줍니다.
  
  
• 1번
  우선 각 줄의 마지막 번째는 각각 1, 3, 6, 10, 15 와 같은 수열로 구성할 수 있습니다. 이를 일반화 시키면 n번째 줄의 마지막 번째는 $\frac{n(n+1)}{2}$ 가 됩니다.
  입력값 X가 $frac{n(n+1)}{2}$ 보다 작거나 같을 경우 X는 n번째 줄에 있다는 의미이므로 while문을 이용해 n을 구해주었습니다.
  
  
• 2번
  if, else 문을 이용해 각각의 케이스를 나누어 주었습니다.
  
  
• 3번
  짝수일 때는 n/1를 홀수일 때는 1/n를 기준으로 하여 입력된 X번째까지와의 차이를 통해 최종 답을 구했습니다.