[boj] 2090. 조화평균 (node.js)

문제 요약

[boj] 2090. 조화평균 (node.js)

• 100을 넘지 않는 자연수 n개(최대 9)가 주어질 때,
• 주어진 모든 자연수에 대해서
  • 분수 형태로 (1 / 자연수) 의 값을 모두 더한 뒤
  • 분모와 분자를 바꾼 결과값을 구하라.
• 이때 표현 가능한 답의 형태 중 기약분수 형태로 출력

풀이

• 문제 풀이의 단계를 두 단계로 나눠볼 수 있다.
  • (1) 주어진 숫자들에 대해 (1 / 자연수) 형태의 총 합을 구하고
  • (2) 구한 합의 역수를 기약분수 형태로 만든다.
• (1) 번 단계에서 총 합을 구할 때 분모, 분자를 각각 합과 곱을 이용헤 구할 수 있고,
• (2) 번 단계에서 기약분수 형태로 만들기 위해 (1)에서 구한 합과 곱의 최대공약수를 유클리드 호제법을 이용해 구한다.
  • 유클리드 호제법
    • a = bq + r
      • gcd(a, b) == gcd(b, r) == ... == gcd(b, 0) == b

내 풀이

const readline = require("readline")
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
})

const solution = () => {
  input()
  const arr = input().split(" ").map(BigInt)
  let mul = arr.reduce((sum, elem) => {
    if (sum % elem == 0 || elem % sum == 0) {
      if (sum > elem) return sum
      return BigInt(elem)
    }
    return sum * elem
  }, 1n)
  let sum = arr.reduce((sum, elem) => sum + mul / BigInt(elem), 0n)
  const gcd = getGCD(mul, sum)
  console.log(mul / gcd + "/" + sum / gcd)

  function getGCD(x, y) {
    let a = x
    let b = y
    if (x < y) (a = y), (b = x)
    let r = a % b
    if (r == 0n) return b
    return getGCD(b, r)
  }
}

let _line = 0
const input = () => stdin[_line++]

let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  solution()
  process.exit()
})