무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
입력 > 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력 > 첫째 줄에 분수를 출력한다.
|예제 입력
1
|예제 출력
1/1
제출
const input = (
process.platform == "linux"
? require("fs").readFileSync("/dev/stdin").toString()
: `4`
).trim();
const X = Number(input);
let limit = 1,
n = 1;
while (limit < X) {
limit += n + 1;
n++;
}
const a = n - (limit - X);
if (n % 2 === 0) {
console.log(`${a}/${n - a + 1}`);
} else {
console.log(`${n - a + 1}/${a}`);
}
풀이과정
이 문제는 X가 몇번줄 몇번째에 있는지 찾으면 되는 문제이다.
진행 순서를 화살표로 표현해보면 왼쪽 그림과 같이 지그재그로 되어있다.
오른쪽은 지그재그 순서대로 했을 때의 번호를 기입한 것이다.
왼쪽 그림과 같이 화살표 한 뭉텅이를 n이라고 했을 때 1번줄에는 1개의 분수, 2번줄에는 2개의 분수, 3번줄에는 3개의 분수, n번줄에는 n개의 분수가 존재한다.
이제 분수의 모양을 구해보자.
n이 짝수일 때, 분자는 1부터 n까지 1씩 증가하고, 분모는 n부터 1까지 1씩 감소하는 모양을 가지고 있다.
ex) n = 2 일 때는 1/2 ▶️ 2/1 n = 4 일 때는 1/4 ▶️ 2/3 ▶️ 3/2 ▶️ 4/1이다.
반대로 n이 홀수일 때는 분자는 n부터 1까지, 분모는 1부터 n의 모양을 가지고 있다.
n이 짝수일 때의 분자, 분모의 모양을 구하면 n이 홀수일 때는 반대로 적용하면 된다.
n번줄 a번째의 분수를 구한다고 할 때,
분모 + 분자 = n + 1 이다.
따라서,분자 = n + 1 - 분모라는 식이 성립된다.
n이 짝수일 때, 분자는 a가 된다.
분자 = n + 1 - 분모 식에 의해서 a = n + 1 - 분모 이다.
따라서 분모 = n - a + 1 식을 얻을 수 있다.
n이 홀수일 때는 짝수일 때와 반대로 분자 = n - a + 1, 분모 = a 가 된다.
분수의 모양을 찾았으니 이제 n과 a를 찾자.
n번 줄에는 n개의 분수가 있기 때문에 n번줄의 가장 마지막 분수는 limit번이다.
따라서 n개의 분수 중, limit과 X의 차이만큼 빼주게 되면 X가 몇번째 요소인지 알 수 있다.
limit과 n은 이전 벌집 문제와 같은 로직으로 구할 수 있고, limit과 n을 구하면 a가 나온다.
