[BOJ] 1193번 - 분수 찾기

사용언어 : javascript - node.js

 

자바스크립트로 푼 알고리즘 문제 중 처음으로 다른 사람이 푼 문제방법으로 문제를 풀었다.

문제를 이해하고 규칙성은 찾았으나, 어떻게 접근해야할 지 모르겠어서 찾아보았다. (한 문제에 질질 끌리는 것보단 빠르게 넘어가는게 좋을 것 같아서.)

 

확인한 규칙성은 아래와 같음

 

여기까진 알아냈는데.. X번째 분자/분모가 감이 안와서 찾아보니 이걸 왜 생각 못했지..라는 생각이 든다.

 

1. 입력한 X는 소속된 라인그룹(1,2,3...)안에 있으며, 앞의 분수들의 번호는 현재 소속된 라인그룹을 다 더한 값이다

  >> 그렇다면 라인그룹 1부터 n-1번 숫자를 더한 값을 이용해 X가 어떤 라인 그룹에 속해 있는지 알 수 있음

2. X에서 앞선 라인그룹을 더한값을 빼면, 해당 라인의 몇번째 분수인지 알 수 있음 (idx)

3. 짝수라인 혹은 홀수라인에서의 분자/분모가 될 수 있는 값은 idx / 라인그룹+1 - idx 임.

 

#제출코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const x = fs.readFileSync(filePath).toString().trim();

solution(+x);

function solution(x) {
  let line = 0;
  let lineSum = 0;

  for (let i = 1; lineSum < x; i++) {
    line = i;
    if (lineSum + i < x) {
      lineSum += line;
    } else {
      break;
    }
  }

  let idx = x - lineSum;

  if (line % 2 === 0) {
    console.log(`${idx}/${line + 1 - idx}`);
  } else {
    console.log(`${line + 1 - idx}/${idx}`);
  }
}

참고 : https://dumbokim.tistory.com/9?category=959940