문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
아이디어
1번째 대각선의 끝: 1번째
2번째 대각선의 끝: 3번째
3번째 대각선의 끝: 6번째
i번째 대각선의 끝: 1 + ... + i번째
입력받은 수가 \displaystyle\sum_{i=1}^{n}i = sum 보다 작거나 같은 경우, i번째 대각선에 속해있음.
이때 분자와 분모의 합은 i + 1
- i가 짝수인 경우 분자는 i, 분모는 1
- sum - x 만큼 분자에 빼준다.
- sum - x 만큼 분모에 더해준다.
- i가 홀수인 경우 분자는 1, 분모는 i
- sum - x 만큼 분자에 더해준다.
- sum - x 만큼 분모에 빼준다.
코드
python
x = int(input())
i, sum = 0, 0
while(1):
sum += i
if x <= sum:
break
i += 1
# 분자와 분모의 합 : i + 1
# 분자: a , 분모: b
if i % 2 == 0:
a, b = i, 1
# sum - x만큼
a = a - (sum - x) # a에는 빼주고
b = b + (sum - x) # b에는 더해준다.
else:
a, b = 1, i
# sum - x만큼
a = a + (sum - x) # a에는 빼주고
b = b - (sum - x) # b에는 더해준다.
print("%d/%d" % (a, b))