[백준 | Java] 9613 GCD 합

내 풀이

최대공약수(GCD)를 찾기 위해서 유클리드 호제법을 사용했다.
이전 최대공약수 문제를 풀 땐 main 안에서 while문을 사용해 나머지가 0이 될 때 까지 작업을 반복했지만,
이번 풀이에서는 최대공약수를 찾는 재귀 형태의 메소드를 작성했다.

유클리드 호제법에 대한 설명은 아래 포스팅에서 확인할 수 있다.

👉🏻 유클리드 호제법 설명 포스팅

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        while (t-- != 0) {
            st = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(st.nextToken());
            int[] arr = new int[n];
            long result = 0;

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

            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    if (i != j) {
                        result += gcd (arr[i], arr[j]);
                    }
                }
            }
            System.out.println(result);
        }
    }

    public static int gcd (int a, int b) {
        if(b == 0)
            return a;

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