BOJ 9613 GCD 합 [Java]

BOJ 9613 GCD 합

- 문제 링크

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

- 문제 해설

3중 for문을 이용하여 풀었다. 시간복잡도가 O(N^2xT)인데, 최대 연산 수가 100x100x100 = 1,000,000 이므로 제한 시간 1초 안에 충분히 가능하다.
최대공약수는 두 수를 입력 받으면 최대공약수를 반환하는 gcd 함수를 유클리드 호제법을 이용하여 만들어 해결했다.
그리고 테스트 케이스마다 주어지는 수들을 다 순회하면서 gcd 함수를 실행하고 그 값을 sum에 더해주어 문제를 해결했다.

- 코드 보기

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

public class Main
{
    public static long gcd(int x, int y)
    {
        if (y == 0)
            return x;
        else
            return gcd(y, x % y);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(st.nextToken());

        for (int i = 0; i < t; i++)
        {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int[] arr = new int[n];
            long sum = 0;

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

            for (int a = 0; a < n; a++)
            {
                for (int b = a + 1; b < n; b++)
                    sum += gcd(arr[a], arr[b]);
            }

            sb.append(sum + "\n");
        }

        bw.write(sb.toString());

        br.close();
        bw.flush();
        bw.close();
    }
}