[알고리즘]백준 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 ≤ X ≤ 10,000,000)가 주어진다.

출력

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

 

풀이

---

2차원 배열의 대각선 성분의 길이는 1씩 늘어납니다. 

처음에는 1/1 1개 두번째에는 2/1 1/2 2개 세번째에는 3/1 2/2 1/3의 3개의 순입니다.

 

처음에는 구하고자 하는 분수가 몇번째 대각선에 위치하는지 구해주겠습니다 

각 대각선의 분수의 분모와 분자는 왼쪽을 기준으로 각각 1씩 차이나는

내림차순과 오름차순입니다(오른쪽을 기준으로 하면 반대) 

 

이 성질을 이용해 쉽게 계산할 수 있습니다

 

한가지 고려해야할 점은 대각선마다 기준점이 바뀐다는 것입니다. 

짝수 대각선에서는 왼쪽에서 오른쪽으로 홀수 대각선에서는 오른쪽을 기준으로 합니다

 

 

import sys

N = int(sys.stdin.readline().strip())
idx= 0
#배열이 몇번째(idx) 대각선에 위치하는지 구해보겠습니다
while N>0:
    idx+=1
    N=N-idx 
#반복문을 통해 1부터 값을 점차 증가시켜가며 빼주겠습니다.
N=N+idx
#반복문을 탈출하면 분수가 위치한 대각선의 배열의 길이만큼 빼줬기 때문에 음수가 나오게됩니다 
#이를 다시 더해주겟습니다. 이때 N은 대각선 배열에서 분수의 순번과 동일합니다 
if idx%2==0:
    nums = list(range(1,idx+1))
    print(f"{nums[N-1]}/{idx-N+1}") 
else:
    nums = list(range(idx,0,-1))
    print(f"{nums[N-1]}/{N}")
#홀수일때와 짝수일때 배열의 방향이 바뀌므로 이를 고려해줍니다