[파이썬] 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)가 주어진다.

출력

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

예제 입력 1 복사

14

예제 출력 1 복사

2/4

 

시간제한 - 0.5초

 

---

일단 우선적으로 고려해야될것들이 있었다

 

1. 무한히 큰 배열

2. 시간제한 0.5초

3. 카운팅을 하는 방향이 항상 같은 방향이 아닌 지그재그 순서라는것

 

처음 생각은 그냥 1부터 하나씩 다 세보는거였는데, 배열이 무한히 크기때문에 수가 어느정도 이상 커지면 바로 시간초과가 뜨게된다.

 

따라서, 특정 조건을 걸어 탐색하는 범위를 줄여야했다.

 

---

표를 잘 보면 알겠지만, 각 칸마다의 분수를 하나의 수로 보거나, 가로 세로로 카운팅하는것이 아닌

 

각 칸에 들어있는 요소가 a / b 로 이루어져있고, a와 b의 범위는 맨 윗줄의 값을 기준으로 좌하단 대각선 방향으로 첫번째값의 분모까지 증가하거나 감소하게된다.

 

다시말해, 맨윗줄 5번째 값인 1/5의 경우, 좌하단 대각선 방향으로 1/5, 2/4, 3/3, 4/2, 5/1 총 5개의 묶음이 만들어지고

a와 b의 범위는 각각 5까지 증가하거나, 5에서 1까지 감소하는 형태로 가게된다.

 

입력받는 수 X는 "X번째 수"를 나타내는데, 각 대각선을 이루는 묶음의 수 n은 배열이 정사각배열이기때문에 첫번째 행의 n번째 값의 대각선 묶음의 수와 같다고 보면 된다.

 

 

자 그럼, X의 정확한 위치를 어떻게 알 수 있을까?

 

X의 대략적인 범위를 구하기 위해서, 예제 14를 확인해보자.

 

14번째 값은 1+2+3+4 < 14 < 1+2+3+4+5 이다.

 

따라서, 첫행의 다섯번째 값을 시작으로 하는 대각선 묶음에 속해있는것을 알 수 있고, 이 묶음의 첫번째값이 몇번째 값인지 구한다면 14번째 값을 바로 구할 수 있을것이다.

---

def solutionSec(X):
    limitCount = 0 #몇번째줄인지
    sum = 0 #합
    #몇번째부터 갈건지 체크
    while sum<X:
        limitCount += 1
        sum = limitCount * (limitCount+1) // 2 #시간복잡도 O(1)

    if limitCount%2 ==0:
        num = X - (sum - limitCount)
        den = limitCount - num + 1
        return "{}/{}".format(num, den)
    else:
        num = X - (sum - limitCount)
        den = limitCount - num + 1
        return "{}/{}".format(den, num)


if __name__ == '__main__':
    number = int(input())
    print(solutionSec(number))

카운팅을 하는 방향이 지그재그이고, 첫번째 행의 n번째 열의 값이 홀수이면 아래에서 위로, 짝수이면 위에서 아래로 순서가 진행되는것을 분기로 if문을 만들어 구분해주면 된다.