<수학1> 1193번 분수찾기 with 파이썬

 

문제

 무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

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

출력

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

정답비율

52.601%

 

 

<코드>

X = int(input())
g = 1 # 그룹의 번호
i = 1 # 그룹에서의 마지막 인덱스
while X > i :
    g += 1
    i += g
# 분자 : N
# 분모 : D
G_index = g - (i - X) # 그룹 내에서의 인덱스
if g%2 == 0 : # 짝수 그룹일 경우
    N = G_index
    D = g - (G_index-1)
else : # 홀수 그룹일 경우
    D = G_index
    N = g - (G_index - 1)

print('{}/{}'.format(N,D))

 

 일단 문제에서 말한 순서대로 분수를 쭉 써보면 분모와 분자의 합이 같은 것끼리 묶을 수 있음을 알 수 있다. 즉 군수열형태이다. 이를 그룹별로 나타내면 다음과 같다.

 

① 1/1 

② 1/2  2/1

③ 3/1  2/2  1/3

④ 1/4  2/3  3/2  4/1

 

 그룹 내의 원소 갯수는 그룹의 숫자만큼 있음을 알 수 있다. 즉 실제 인덱스는 이전 그룹의 번호가 계속 더해진 것이다.

 

 그리고 분모와 분자를 쪼개보자. 홀수 그룹에서는 분모가 1씩 증가하고 분자가 1씩 감소하는 형태이다. 짝수 그룹에서는 그 반대이다.

 

 while문을 통해 그룹과 실제 인덱스를 구해주었다.

 

 그리고 분자(Numerator)는 N이라는 변수로 분모(Denominator)는 D라는 변수로 나타내었다.

 

 입력받은 숫자의 그룹 내 인덱스가 필요하여 G_index로 나타내었고, 짝수그룹인지 홀수그룹인지에 따라 분모와 분자를 각각 구하였다.

 

 

---

 

 

 

참고

 

1193번: 분수찾기