[Baekjoon] 9613 GCD 합(자바스크립트/NodeJs)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

9613번: GCD 합

---

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

예제 입력 1

3
4 10 20 30 40
3 7 5 12
3 125 15 25

예제 출력 1

70
3
35

---

정답 코드

나의 답안

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let [t, ...input] = fs.readFileSync(filePath).toString().trim().split('\n');

t = parseInt(t);

const mySolution = (t, data) => {
    const gcd = (a, b) => {
        // let r;

        // while (b > 0) {
        //     r = a % b;
        //     a = b;
        //     b = r;
        // }

        // return a;

        if (b === 0) return a;

        return gcd(b, a % b);
    };

    for (let i = 0; i < t; i++) {
        const nums = data[i].split(' ');
        const n = parseInt(nums[0]);
        let sum = 0;

        for (let j = 1; j < n; j++) {
            const a = parseInt(nums[j]);

            for (let k = j + 1; k <= n; k++) {
                const b = parseInt(nums[k]);
                sum += gcd(a, b);
            }
        }

        console.log(sum);
    }
};

console.log('mySolution');
mySolution(t, input);

답안 1

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let [t, ...input] = fs.readFileSync(filePath).toString().trim().split('\n');

t = parseInt(t);

const answer1 = (t, input) => {
    const gcd = (a, b) => {
        if (a % b === 0) return b;
        return gcd(b, a % b);
    };

    const getSum = (n, ...arr) => {
        let sum = 0;

        arr.sort((a, b) => b - a);
        arr.forEach((v, i) => {
            while (i < n - 1) {
                sum += gcd(v, arr[++i]);
            }
        });

        console.log(sum);
    };

    input.forEach((v) => {
        getSum(...v.split(' ').map((val) => parseInt(val)));
    });
};

console.log('answer1');
answer1(t, input);

답안 2

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let [t, ...input] = fs.readFileSync(filePath).toString().trim().split('\n');

t = parseInt(t);

const answer2 = (t, input) => {
    const gcd = (a, b) => {
        if (b === 0) return a;

        return a > b ? gcd(b, a % b) : gcd(a, b % a);
    };

    input.forEach((v) => {
        v = v.split(' ');
        const n = parseInt(v.splice(0, 1));
        const nums = v.map((val) => parseInt(val));
        let sum = 0;

        for (let i = 0; i < n - 1; i++) {
            for (let j = i + 1; j < n; j++) {
                sum += gcd(nums[i], nums[j]);
            }
        }

        console.log(sum);
    });
};

console.log('answer2');
answer2(t, input);

---

문제 풀이

 각 테스트 케이스의 숫자 조합마다 최대공약수를 구해 그 값들을 모두 더하여 반환하면 되는 문제이다.

 입력값이 10 20 30 40일 때 나올 수 있는 숫자의 조합은 다음과 같다.

10 20
10 30
10 40
20 30
30 40

 나의 경우  for문을 3번 돌면서 입력값을 정제했다. 즉 a와 b에 두 수를 번갈아 넣으면서 두 수의 최대공약수를 모두 더한 값이 정답이 되는 것이다. 최대공약수를 구할 때는 유클리드 호제법을 사용했다.

---

함께 보기

최대공약수를 구하는 방법들

https://gdk01.tistory.com/137

[Programmers] level 1: 최대공약수와 최대공배수 by JavaScript

https://gdk01.tistory.com/224

[Baekjoon] 2609 최대공약수와 최소공배수(파이썬/자바스크립트/NodeJS)

https://gdk01.tistory.com/225

[Baekjoon] 1934 최소공배수(파이썬/자바스크립트/NodeJS)

 

참고 포스팅

https://tesseractjh.tistory.com/110

[백준 9613] GCD 합 with Node.js

https://tesseractjh.tistory.com/110

[백준 9613] GCD 합 with Node.js