알고리즘 기초 1/2. 301 - 수학 1(연습)
9613번. GCD 합

문제

9613번 문제 링크

solution

const fs = require("fs");
let inputs = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const iter = Number(inputs.shift());

let ans = [];

// 유클리드 호제법을 함수로 구현해놓음.
function getGCD(a, b){
    
    while(a % b !== 0){
        let r = a % b;
        
        if(r !== 0){
            a = b;
            b = r;
        }
    }
    
    return b;
}

for(let i = 0; i < iter; i++){
    let input = inputs[i].trim().split(" ").map((item) => Number(item));
    
    let newIter = input.shift();
    
    // 유클리드 호제법은 앞에 있는 수가 뒤에 있는 수보다 크거나 같은 것이 조건이므로
    // 내림차순 정렬을 해준다.
    input.sort((a ,b) => b - a);
    
    let sum = 0;
    
    // 두 수를 비교해서 최대공약수를 구하는데
    // 만약, 4개의 숫자가 있다면
    // 앞에 올 숫자는 1,2,3번째 숫자를 가지고
    for(let j = 0; j < newIter - 1; j++){
        let a = input[j];
        
        // 뒤에 올 숫자는 2,3,4번째 숫자를 가져야지, 중복이 되지않는다.
        // 즉, 1번째 숫자와 1번째 숫자를 조합하는 일은 없게 만든다는 뜻이다.
        for(let k = j + 1; k < newIter; k++){
            let b = input[k];
            
            // 유클리드 호제법
            let GCD = getGCD(a, b);
            
            sum += GCD;
        }
    }
    
    ans.push(sum);
}

console.log(ans.join("\n"));

참고 자료

참고 자료 1