[알고리즘] 백준 1193번, 분수 찾기, 재귀 함수, python(16)

 

문제를 어렵게 생각한 거 같은 느낌(항상 그렇지만). 어렵게 생각하지만 푸는 건 빠르니까 상관없나..?

 

분수들이

 

1/1

1/2
2/1

3/1
2/2
1/3

1/4
2/3
3/2
4/1

 

이렇게 1,2,3,4 뭉치로 iteration이 존재해서 우리가 원하는 number가 어떤 iteration에 속하는지 파악하는 게 핵심이다. 

구글링 찬스를 쓴 부분은 짝수 홀수를 구별하는 게 순간 생각이 안 나서 찾아봄

 

if number % 2 == 0

이걸로 쉽게 해결

def fraction(number):
    n = 1
    while True:
        if number == 1:
            return (0,0)
        elif n*(n+1)/2 >= number:
            return((int(n*(n-1)/2)),n)
        else:
            pass
        n += 1
        
number = int(input())
result_sum,n=fraction(number)

if number == 1:
    print('1/1')
elif (n)%2 == 0:    
    jump = number - result_sum
    print ('{}/{}'.format(jump,(n+1-jump)))
else:
    jump = number - result_sum
    print ('{}/{}'.format((n+1-jump),jump))