문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

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

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

예제 입력

14

예제 출력

2/4

내가 했던 풀이 방법

1. 1부터 N까지 while문을 사용하여 분모 또는 분자가 1일 때와 아닐 때를 나누어서 풀이 -> 실패 (시간초과) 아래 답변을 참고하여 방법을 떠올림.
   

2-1. 1부터 1씩 늘린 수의 합이 N 이상이 될 때, 마지막으로 더한 수-1와 합에서 마지막으로 더한 수를 뺀 값을 각각 num과 sum에 저장해둔다. (즉, N이 5일 경우, 1+2+3까지 수행했을 때 N이상이 되므로, num에는 3-1=2, sum에는 1+2=3을 저장한다.)
2-2. 만약 num이 짝수일 경우, 시작하는 분수를 1/num으로 설정하고, sum+1부터 N까지 분자를 1씩 더해주고 분모를 1씩 빼준다. (sum+1부터 하는 이유는 시작하는 분수가 sum번째 수이기 때문이다. 만약 N이 sum과 같을 경우 for문을 수행하지 않고 바로 출력된다.)
2-3. num이 홀수일 경우, 시작하는 분수를 num/1으로 설정하고, sum+1부터 N까지 분자를 1씩 빼주고 분모를 1씩 더해준다.

코드

var fs = require('fs');
var N = fs.readFileSync('/dev/stdin').toString().trim();

let num = 1;
let sum = 0;
while (true) {
  if (sum >= N) {
    sum -= --num;
    break;
  }
  sum += num++;
}

let split = [];
let start = '';
if (num % 2 === 0) {
  start = 1 + '/' + num;
  for (let i = sum + 1; i < N; i++) {
    split = start.split('/');
    start = parseInt(split[0]) + 1 + '/' + (parseInt(split[1]) - 1);
  }
} else {
  start = num + '/' + 1;
  for (let i = sum + 1; i < N; i++) {
    split = start.split('/');
    start = parseInt(split[0]) - 1 + '/' + (parseInt(split[1]) + 1);
  }
}

console.log(start);

회고

수학적으로 접근하니까 코드가 엄청 간소화되었다. 처음 풀이했을 때는 코드를 보기도 힘들정도로 엄청 복잡하고 더러운 코드였는데 (시간초과가 될 걸 알고 있었지만, 정말 생각나는 방법이 없었던터라..) 정말 풀이 방법이 생각 안 나서 질문 게시판에 들어가보니 저런 좋은 참고 답변이 있어서 바로 방법이 떠올랐다. 사람들은 정말 이 방법을 어떻게 떠올리나... 대단한 사람들이 많은 것 같다.