[백준 9613번 GCD 합 - node.js] [알고리즘 기초 1/2]

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

9613번: GCD 합

 

문제

 

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

 

입력

 

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

 

출력

 

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

 

예제 입출력

 

입력	출력
3 4 10 20 30 40 3 7 5 12 3 125 15 25	70 3 35

 

풀이[node.js]

 

 

728x90

이번 문제는 이전의 최소공배수에서 풀었던 방식으로 간단하게 풀어보았습니다.

입력되는 값들을 gcd function에 각각 보내주어 최대공약수를 구한 후, 결과값을 result에 더한 후, answer에 각각 줄에 대한 result값을 더해주었습니다.

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(inputs[0]);
var answer = [];
for(var i=1; i<=cases; i++){
    var splited = inputs[i].split(' ');
    var nums = Number(splited[0]);
    var result = 0;
    for(var j=1; j<=nums; j++){
        for(var k=j+1; k<=nums; k++){
            var common = gcd(Number(splited[j]), Number(splited[k]));
            result += common;
        }
    }
    answer.push(result);
}
console.log(answer.join('\n').trim());
var tmp;
function gcd(a,b){
    while(b != 0){
        tmp = a%b;
    	a = b;
    	b = tmp;
    }
    return a;
}