[백준/Java] 9613 GCD 합 (feat. 유클리드 호제법)

문제

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

# 입력

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

# 출력

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

 

 

 

---

 

 

 

문제에서 말하는 GCD란?

Greatest Common Divisor, 즉 최대공약수를 말한다.

 

그리고 여기서 새롭게 알게 된 알고리즘 "유클리드 호제법" 에 대해 소개하려 한다.

유클리드 호제법은, 주어진 두 수 사이에 존재하는 최대공약수 (GCD) 를 구하는 알고리즘이다.

 

유클리드 호제법의 원리는 다음과 같다.

비교대상 두 개의 자연수 a와 b에서 a를 b로 나눈 나머지를 r이라고 했을 때,
GCD(a, b) = GCD(b, r) 과 같고 r이 0이면 그때 b가 최대공약수이다.

 

유클리드 호제법의 장점은 빠르다는 것이다!

일반적으로 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(a,b)까지 모든 정수로 나누어 보는 방법이 있는데,

이같은 경우 모든 정수를 나눠야 하므로 시간 복잡도는 0(N)이 된다.

 

하지만 유클리드 호제법을 사용한다면 비교대상의 두 수에서 a를 b로 나눈 나머지를 r 이라 했을 때,

a%r = 0 이 될 때까지 반복해주는 방식으로 시간 복잡도를 O(logN)으로 줄일 수 있다.

 

 

풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static int euclidean(int a, int b) {
		if(b == 0)
			return a;
		else
			return euclidean(b, a % b);
	}

	public static long GCD(StringTokenizer st) {
		long result = 0;
		int n = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];

		for(int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < n; i++) { 
			for(int j = i + 1; j < n; j++) {
				result += euclidean(arr[i], arr[j]);
			}
		}

        return result;
	}

    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		while(n-- != 0) {
			System.out.println(GCD(new StringTokenizer(br.readLine())));
		}
	}
}

 

 

© 참고

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

https://coding-factory.tistory.com/599

9613번: GCD 합