백준 js 6913: 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

풀이

1번째 줄에 총 몇개의 테스트 케이스가 주어지는 지가 나와있고,

1번째 줄 제외 모든 줄 맨 앞에는 각 몇개의 수가 올지 나와있다.

그렇기 때문에 이 두 수를 제외한 모든 수의 쌍을 만들어서 그 쌍의 최대공약수를 구하면 된다.

예를 들면

두번 째 줄에 10, 20, 30, 40 에선

10, 20

10, 30,

10, 40

20, 30

20, 40

30, 40

로 총 6개의 쌍을 만들 수 있고, 각 쌍의 최대공약수들의 합을 출력하면 된다.

 

+ 이 문제에서 엄청 헤맸었는데, 

아무리 봐도 맞았고, 테스트 케이스도 다 맞다고 나오는데, 제출하면 계속 틀렸다고 나왔다..

결국 문제는 인풋값에 trim을 해줘야 했던 것이다..🤬

 

다른 js로 알고리즘 푼 사람들을 보면 trim()을 꼭 해주던데, 

그 전까지는 그 이유를 딱히 몰랐는데..

 

유클리드 호제법을 이용해서 GCD를 구할 수 있는 함수를 만들어준다.

const getGCD = (a, b) => {
	let r;
    while(b) {
    	r = a%b;
        a = b;
        b = r;
    }
    return a;
}

 

각 쌍을 구해 그 값의 최대공약수를 구하는 부분

/*
input = [
  [ '10', '20', '30', '40' ],
  [ '7', '5', '12' ],
  [ '125', '15', '25' ]
]
*/

// input loop
for (let i = 0; i < input.length; i++) {
	// input[i] loop: length - 1은 i와 i+1를 비교하기 때문
    for (let j = 0; j < input[i].length - 1; j++) {
    	for (let k = i + 1; k < input.[i].length; k++) {
        	eachResult += getGCD(+input[i][j],+input[i][k]);
        }
    }
    console.log(eachResult);
    eachResult = 0;
}

 

전체 코드

 

	const fs = require("fs");
	let input = (process.platform === "linux"
	? fs.readFileSync("/dev/stdin").toString().trim()
	: `3
	4 10 20 30 40
	3 7 5 12
	3 125 15 25`
	)
	.split("\n")
	.map((x) => x.split(" "));
	input.shift();
	input.map((x) => x.shift());
	const getGCD = (a, b) => {
	let r;
	while (b !== 0) {
	r = a % b;
	a = b;
	b = r;
	}
	return a;
	};
	let tmp = 0;
	for (let i = 0; i < input.length; i++) {
	for (let j = 0; j < input[i].length - 1; j++) {
	for (let k = j + 1; k < input[i].length; k++) {
	tmp += getGCD(parseInt(input[i][j]), parseInt(input[i][k]));
	}
	}
	console.log(tmp);
	tmp = 0;
	}

view raw 9613.js hosted with ❤ by GitHub