백준 27437 - 분수찾기 2

https://www.acmicpc.net/problem/27437

힌트

문제에 그려진 테이블을 유심히 보자.

 

 

위와 같이 구분한다고 했을 때 패턴을 찾아낼 수 있는가?

풀이

위 힌트에서 주어진 테이블을 대각선으로 나눴다. 그러면 우리는 각 대각선에서 발견할 수 있는 중요한 성질을 다음과 같이 정리할 수 있다.

 

각 대각선에 속한 수들의 집합을 $D_{1}, D_{2}, D_{3}, ...$으로 부르며 원소의 갯수는 $1, 2, 3, ...$이다.

 

이때 $D_{i}$의 원소인 $\frac{y}{x}$에서 $MAX(x, y) = i$이다.

 

우리는 $\sum_{i = 1}^{n}\nolimits i \leq X$를 만족하는 $i$의 최댓값을 파라메트릭 서치로 찾아낼 수 있다.

 

그리고 대각선을 문제의 규칙에 따라 분자가 제일 큰 게 먼저, 분모가 제일 큰 순으로 나열함으로 분류할 수 있고 1씩 변화한다는 특징을 통해 $X$번째 분수를 바로 계산할 수 있다.

 

시간 복잡도: 파라메트릭 과정을 통해 적절한 $i$를 찾으므로 $O(\log X)$

 

정답 코드 - python

def find_term(n: int):
    lo = 1
    hi = 10 ** 18
    ret = 0
 
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        prog = (1 + mid) * mid // 2
        if n > prog:
            lo = mid + 1
        else:
            hi = mid - 1
            ret = mid
    
    return ret
 
 
def solve():
    x = int(input())
    if x == 1:
        print (f'1/1')
        return
    
    term = find_term(x)
    num = term
    deno = 1
    
    pref = (1 + (term - 1)) * (term - 1) // 2
    x -= pref
    num -= x - 1
    deno += x - 1
 
    if (term & 1) == 0:
        num, deno = deno, num
 
    print(f'{num}/{deno}')
 
 
if __name__ == "__main__":
    solve()