[백준JS] 1735. 분수 합

안녕하세요. 박기린 입니다.

백준 1735번 분수 합 문제를 풀어봅시다.

 

 

문제 링크

https://www.acmicpc.net/problem/1735

 

 

---

문제 해석

최대공약수를 구하면 기약분수를 바로 구할 수 있습니다.

두 분수를 더한 다음, 분모와 분자의 최대 공약수를 구하고, 분모와 분자를 각각 최대공약수로 나눠주면 기약분수가 됩니다.

 

최대공약수는 유클리드 호제법으로 구하면 됩니다.

// 유클리드 호제법으로 최대공약수를 구하는 식
const gcd = (x, y) => {
  if (y == 0) return x;
  else return gcd(y, x % y);
};

 

 

 

---

정답 코드

const fs = require("fs");
const [moles, denoms] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let [fM, fD] = moles.split(" ").map(BigInt);
let [sM, sD] = denoms.split(" ").map(BigInt);

let mole = fM * sD + sM * fD;
let denom = fD * sD;

const gcd = (x, y) => {
  // console.log(x, y)
  if (y == 0) return x;
  else return gcd(y, x % y);
};

const divisor = gcd(mole, denom);

console.log(`${mole / divisor} ${denom / divisor}`);

 

 

 

---

정답 코드 풀이

const fs = require("fs");
const [moles, denoms] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let [fM, fD] = moles.split(" ").map(BigInt);
let [sM, sD] = denoms.split(" ").map(BigInt);

fM, fD : 첫 번째 분수의 분자와 분모입니다.

sM, sD: 두 번째 분수의 분자와 분모입니다.

 

 

 

let mole = fM * sD + sM * fD;
let denom = fD * sD;

mole과 denom은 두 분수를 합한 후의 분자와 분모입니다.

 

 

 

const gcd = (x, y) => {
  // console.log(x, y)
  if (y == 0) return x;
  else return gcd(y, x % y);
};

const divisor = gcd(mole, denom);

유클리드 호제법을 이용해서 분자와 분모 간의 최대공약수를 구합니다.

 

 

 

console.log(`${mole / divisor} ${denom / divisor}`);

최대공약수로 분자와 분모를 나눈 후 출력을 하면 끝입니다.