BOJ 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번째 분수를 구하는 프로그램을 작성하시오.

if __name__ == '__main__':
    x = int(input())
    
    sum_n = 0

    n = 0

    while not (n-1*(n)/2 < x <= (n)*(n+1)/2) :
        n += 1


    if n % 2 == 0:
        print(f'{int(n + (x - n *(n+1) / 2))}/{int(abs(x - n *(n+1) / 2) + 1)}')
    else:
        print(f'{int(abs(x - n *(n+1) / 2) + 1)}/{int(n + (x - n *(n+1) / 2))}')

분수 찾기라고 되어 있지만, 자세히 보면 군수열(Gropuing)에 관한 문제였다. 1군 .. 2군 .. 3군 .. 순으로 순서 특징을 찾아내면 된다. 나는 먼저 해당 군을 찾고, 그  군에서 지금 X가 몇 번째 인지를 찾았다. 그리고 지그재그로 움직이기 때문에 귀찮아서 그냥 홀수, 짝수 일 때의 조건을 부여했다.

 

이걸 풀면서 갑자기 든 생각은 수학이 중요하고, 고등학교 때 배웠던 그 기억이 갑자기 새록새록 나서 다행이라는 생각을 했다. 또 고등학교 때 배우지 않았더라면 이런 아이디어를 낼 수도 없었을 것이라 생각하고, 공부하길 잘했다는 생각을 한다. 근데 이걸 인공지능이 풀 수 있을까? 규칙을 금방 찾아낼 거 같은데... 언젠가 한번 try 해봐야지..