1193

제목 : 분수찾기

• 문제 : 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

• 입력 : 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
• 출력 : 첫째 줄에 분수를 출력한다.

주어진 분수들을 지그재그로 순열을 만들었을 때 X번 째 분수를 찾아야 하는 문제이다. 사선으로, 방향을 바꿔가며 순열이 주어지는 상황인데 이게 말로하면 와닿지 않을 수 있다. 하지만 이걸 다음과 같이 묶어서 표현하면 이해가 쉽게 갈 것이다. (1/1) → (1/2 → 2/1) → (3/1 → 2/2 → 1/3) → (1/4 → 2/3 → 3/2 → 4/1) → …

라떼는 이걸 군수열(group sequence)라고 고등학교 수학 때 배웠었는데 요즘도 배우는지 모르겠다. 요 근래 고교수학 과정이 가벼워 지고 있다는 얘길 들어서 …

하여간 군수열로 접근하면 문제는 간단해진다. X를 받았을 때 알아야할 것은

1. 몇 번째 군(group)에 속하는가?
2. 해당 군 내에서 몇 번째 수열인가?

이다.

각 군은 공차 1의 등차수열로 이루어진 원소 갯수를 포함한다. 즉 {a_n}에 속한 원소의 갯수는 sum(n)이다. 만약 X=7이라면, (1+2+3) < 7 ≤ (1+2+3+4) 이기 때문에 {a_4}에 속한다는 걸 알 수 있다. 이런식으로 1번은 해결할 수 있다. 두 번째 요소인 “해당 군 내에서 몇 번째 수열인가?” 또한 이런식으로 해결 할 수 있다.

X=7일 때, X가 4번 군에 속한다는 사실을 앞서 말한 방식으로 알아내었다. 그렇다면 그 이전 군인 3번군까지 속한 원소의 갯수를 X에서 빼주면 간단하게 몇 번째 원소인지도 알 수 있다. 3번 군까지 속한 원소의 갯수는 1+2+3=6이므로 7-6 = 1, 즉 첫 번째 원소라는걸 쉽게 알 수 있다.

그렇다면 X=7일 때 정답은 어떻게 구할까? 첫 번째 군은 (1/1), 두 번째 군은 (1/2, 2/1), 세 번째 군은 (3/1, 2/2, 1/3) … 규칙이 보이는가?

맞다. 각 군의 분자와 분모의 합은 동일하며, 그 합은 공차가 1인 등차수열을 이룬다. 또한 짝수번 째 군은 분자가 1로 시작하며 홀수번 째 군은 분모가 1로 시작한. 우리는 이미 주어진 X=7가 4번 째 군의 첫 번째 원소라는 사실을 알고 있다. 이를 통해 4번 군은 분자+분모 = 5라는 사실과 분자가 1로 시작하는 걸 알고 있으므로 답은 1/4라는걸 유추할 수 있다!

코드는 다음과 같다.

import sys
n = int(sys.stdin.readline())

if n==1:
    group = 1
    nth=0
else:
    i=1
    j=1
    while n>j:
        i+=1
        j+=i
    group = i
    nth = n-j+i-1

if(turn%2==1):#홀수
    a = group - nth
    b = nth + 1
else:
    a = 1 + nth
    b = group+1 -a

print('%d/%d'%(a, b))

코드 자체는 훨씬 효율적으로 짤 방법이 있겠지만, 솔직히 말해서 이게 직관적으로 이해도 쉽고… 무엇보다 문제에서 그런걸 요구하지 않는다. 라는 변명을 덧붙인다.