<백준 문제풀이: 1193번> 파이썬 - 분수찾기

옛날에 한번 풀때는 굉장히 고민을 많이 했던 문제이지만, 계속 공부하고 이제 다시 보니 풀이 방법이 조금 더 쉽게 보였다:

import sys

X = int(sys.stdin.readline())

num_list = [1]

add = 1
while True:
    if max(num_list) <= X:
        num_list.append(max(num_list) + add)
        add += 1
    elif max(num_list) > X:
        break
if X == 1:
    print('1/1')
else:
    if num_list.index(num_list[-2])%2 == 0:
        answer = str(num_list.index(num_list[-2])+1-(X-num_list[-2])) + '/' + str(1+(X-num_list[-2]))
        print(answer)
    elif num_list.index(num_list[-2])%2 != 0:
        answer = str(1+(X-num_list[-2])) + '/' + str(num_list.index(num_list[-2])+1-(X-num_list[-2]))
        print(answer)

우선 그림에 나와있는 분수 표를 보자. 순서대로 본다면 1번째 - 1/1, 2번째 - 1/2, 4번째 - 3/1, 7번째 - 1/4, 11번째 - 5/1... 이렇게 보듯이, 새로운 대각선에 첫번째로 정의되는 분수는, 1, 2, 4, 7, 11로 계차수열을 이룬다. 즉, 공차가 1, 2, 3 ,4 로 하나씩 늘어나는 등차수열인 계차수열이다.
따라서 이를 해결하기 위해서는 우선 num_list=[1]을 정의해주고, add=1로 정의를 해준다. while문을 돌려서, 우리가 찾고자하는 X번째 숫자가, 어느 대각선에서 시작되는지 찾아볼 수 있다. 예를 들어보자:

만약 X가 14라면, 우리는 14번째 숫자를 찾고 싶을 것이다. 여기서 while문을 돌리게 된다면, 우리의 num_list는 다음과 같이 나올 것이다: [1, 2, 4, 7, 11, 16] 그렇다면 이제 우리가 알 수 있는 것은, 14번째 숫자는, 11번째 숫자가 시작되는 대각선에서 정의되어 있을 것이다.

그렇다면 여기서 우리는 해당 대각선의 index값을 통해, 분자가 오름차순으로 늘어나는 순서를 가진 대각선인지, 아니면 분모가 오름차순으로 늘어나는 순서를 가진 대각선인지 판별 할 수 있다. 만약 해당 숫자가 들어가있는 대각선의 index가 2의 배수가라면, 분모가 오름차순으로 늘어나는 대각선에 속해 있는 것이고, index가 2의 배수가 아닌 홀수라면, 분자가 오름차순으로 늘어나는 대각선에 속해 있는 것일 것이다. 이에 따라 알맞게 식을 써주면 된다.