[백준 / nodejs] 1193번 : 분수찾기

1193번: 분수찾기

문제

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

풀이

이미지를 보며 알 수 있는 것들을 나열해 보겠습니다.

 

각 n에 해당하는 분자와 분모를 살펴봅시다.

n = 1     1/1

n = 2     1/2   2/1

n = 3     3/1   2/2   1/3

n = 4     1/4   2/3   3/2   4/1

 

다음의 정보를 알 수 있습니다.

• n 은 1씩 증가합니다.
• n이 짝수면 분자가 1부터 시작합니다. 마지막 값은 n입니다.
• n이 홀수면 분모가 1부터 시작합니다. 마지막 값은 n입니다.
• 분자 + 분모 = n + 1

풀이 순서

1. input이 속하는 n 번째 줄 구하기 ( n의 값 구하기)
   
   • n번 째 줄의 최대값(max) 구하기
2. n이 짝수일 때 
   • 분자는 1부터 n까지 증가합니다.  
   • 분자 = n - (max - input)
   • 분모 = n + 1 - 분자   (분자 + 분모 = n + 1 의 응용)
3. n이 홀수일 때
   • 분모는 1부터 n까지 증가합니다. 
   • 분모 = n - (max - input)
   • 분자 = n + 1 - 분모   (분자 + 분모 = n + 1 의 응용)

코드

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

let n = 0;

let max = 0;
//* n번째 줄인지, 그리고 최대값은 얼마인지 구하는 while문
while (max < Number(input)) {
  n++;
  max = max + n;
}

let 분자 = 0;
let 분모 = 0;

if (n % 2 === 0) { // n이 짝수일 때
  분자 = n - (max - input);
  분모 = n + 1 - 분자;
} else { // n이 홀수일 때
  분모 = n - (max - input);
  분자 = n + 1 - 분모;
}

console.log(`${분자}/${분모}`);

참고한 블로그

[백준] 1193: 분수찾기 (javascript)