[백준9613_자바스크립트(javascript)] - GCD 합

🔴 문제

GCD 합

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [_, ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const GCD = (a, b) => (b === 0 ? a : GCD(b, a % b));

for (const [n, ...input] of inputs) {
  let ans = 0;

  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      ans += GCD(input[i], input[j]);
    }
  }

  console.log(ans);
}

🟢 풀이

⏰ 소요한 시간 : -

이 문제를 일반적인 GCD를 구하는 방법대로 풀이하면 무리 3중 중첩 반복문으로 O(n^3)의 풀이가 나온다.
따라서 GCD를 더 빠르게 구하는 유클리드 호제법으로 풀이한다.

const GCD = (a, b) => (b === 0 ? a : GCD(b, a % b));

🔵 Ref