[JS]백준 1193번 분수찾기

출처

https://www.acmicpc.net/problem/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번째 분수를 구하는 프로그램을 작성하시오.

풀이

3일 동안 안 풀린 문제입니다. 결국 다른 분들의 정답을 참고하였습니다. 어떻게 이런 생각을 하신지 모르겠습니다.

문제의 핵심은 구간을 나누는 것입니다. 분수에 규칙이 있는데 최댓값에 따라서 1,2,3,4 이렇게 증가하는 모양을 같는다는 것입니다. 따라서,

1. 해당 숫자가 어떤 구간에 해당하는지?

2. 그 구간에서 나오는 숫자 오름차순, 내림차순 정렬

3. array에서 뽑아서 분수 완성하기

순서대로 풀었습니다. x + groupCounter을 통해 해당 index에 접근하는 과정은 아직도 신기하고 어떻게 이런 생각을 했는지 궁금합니다.

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString();
let x = Number(input);
let groupCounter = 0;

const 오름차순 = [];
const 내림차순 = [];
while (x > 0) {
    groupCounter++;
    x = x - groupCounter;
    console.log(x, groupCounter)
}

for (i = 0; i < groupCounter; i++) {
    오름차순.push(i + 1);
    내림차순.push(groupCounter - i);
    console.log(오름차순, 내림차순)
    if (groupCounter % 2 === 0) {
        console.log(`${오름차순[x + groupCounter - 1]}/${내림차순[x + groupCounter - 1]}`)
    } else {
        console.log(`${내림차순[x + groupCounter - 1]}/${오름차순[x + groupCounter - 1]}`)
    }
}

제가 시도한 흔적입니다...

const fs = require('fs');
const input = Number(fs.readFileSync('/dev/stdin').toString());

let i = 1;
let j = 1;
let n = 1;
let arr = [];

while (true) {
    n = n + i;
    if (input < n) {
        let ans = n - 1;
        while (true) {
            ans = ans - j;
            if (ans === 0) {
                for (k = 1; k <= j; k++) {
                    arr[k - 1] = k;
                }
                if (j % 2 === 0) {
console.log(`${arr[input - arr.length - 1]}/${arr[arr.length + 1]}`)
} else {}
                break;
            }
            j++;
        }
        break;
    }
    i++;
}

console.log(i,j,n);