백준 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 이상, 10,000,000 이하)가 주어진다.

출력

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

 

 

# 해결법

표를 지그재그로 이동하면서 라인을 세면 첫 번째 라인까지의 총 갯수 합, 두 번째 라인까지의 총 갯수 합~ 이

1, 3, 6, 10, 15.. 순으로 증가한다.

cnt에서 2를 더할경우 사선에서 두번째 라인, 3을 더할 경우 세번째 라인이다.

이것을 생각해서 입력값의 바로 직전라인까지의 총 갯수 합을 빼버리면 입력값이 해당 라인의 몇번째에 위치하고 있는지 알 수 있다.

그 다음에는 지그재그로 이동하는 것을 고려하여 cnt 변수를 짝수와 홀수로 나누어 분모와 분자를 거꾸로 바꿔주었다.

 

# 나의 코드

a = int(input()) # 입력
num = 0 # 1, 3, 6, 10, 15... 순으로 증가하는 라인별 총 수
cnt = 1 # num값을 2, 3, 4... 씩 순차적으로 더해주기 위한 변수

while a > num : # 입력받은 값이 num값보다 큰 동안
    num += cnt # num = num + cnt
    cnt += 1 # cnt는 1씩 증가

b = a - (num - (cnt - 1)) # b = 라인에서 몇 번째

# 짝수와 홀수로 나누어서 지그재그 구현
if cnt % 2 == 0: 
    print(str(cnt-b)+'/'+str(b))
else:
    print(str(b)+'/'+str(cnt-b))