[JavaScript] 백준 코딩테스트 1193. 실버 5 : 분수 찾기

📌  문제

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

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)가 주어진다.

📌  출력

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

📌  예제 입출력

---

📌  풀이

알아야 하는 것

문제를 잘 이해해야 한다.

아래 그림처럼 지그재그 형식으로 전개된다.

이 때 각 층을 1/1부터 1층이라고 할 때,

[2층] 2/1 1/2

[3층] 3/1 2/2 1/3

이렇게 구분 지을 수 있다.

 

또 층이 짝수냐 홀수냐에 따라서 전개되는 방식이 다르다.

2층의 경우 1/2 -> 2/1 로 분모가 1씩 작아지고 분자가 1씩 증가한다.

반면 3층의 경우 분모가 1씩 증가하고 분자가 1씩 감소한다.

구할 것

• 주어진 수가 몇 층에 속하는지
  • while문으로 num에 step을 계속 빼주면서 num이 0보다 작거나 같아질 때를 찾는다.
  • 예를 들어 2라고 하면 num = -1, step = 2가 나오게 된다. 같은 층에 있는 3은 num = 0, step = 2로 약간의 규칙이 보인다.
  • 만약 다른 층에 있는 4라고 하면 num = -2, step = 3이 나온다. 5는 num = -1, step = 3이 나온다.
• 짝수 층 홀수 층 차이
  • 즉 짝수 층이면 분자가 step에서 하나씩 작아지고, 분모가 1에서 하나씩 커진다.
  • 홀수 층이면 분자가 1에서 하나씩 커지고, 분모가 step에서 하나씩 작아진다.
  • 이러한 전개는 num이 0보다 크거나 같아지면 때까지 반복된다.
  • 예를 들어 짝수 층인 숫자 2를 보면 num = -1로 1번만 반복되면 된다. 2-> 1 / 1 -> 2로 1/2가 나온다.
  • 다른 예시인 홀수 층 숫자 4를 보면 num = -2로 2번 반복한다. 1 -> 2 -> 3 / 3 -> 2 -> 1로 3/1이 나온다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

let num = Number(input);
let step = 0;

while (num > 0) {
  step++;
  num = num - step;
}

const isEvenStep = step % 2 === 0;

let up, down;
if (isEvenStep) {
  up = step;
  down = 1;
  while (num < 0) {
    up--;
    down++;
    num++;
  }
} else {
  up = 1;
  down = step;
  while (num < 0) {
    up++;
    down--;
    num++;
  }
}

console.log(`${up}/${down}`);

 

방탈출마냥 규칙을 찾는 문제였다.