백준 9613 자바 - GCD 합 (boj 9613 java)

문제 : boj9613

 

  우선 모든 쌍을 확인하는게 이 가능할지 확인해보자. n은 최대 100 이므로 모든 쌍을 확인할 경우 O(n^2)이 필요하고, 총 t개의 테스트케이스가 존재하므로 O(100*100^2) 이므로 충분히 가능하다. 그럼 뭐 어렵게 생각할 것 없이 무지성으로 모든 쌍을 확인해보면 된다.

 

  모든 쌍 확인은 예를들어 배열의 길이가 5일 경우 인덱스는 0,1,2,3,4가 존재할 것이다. 그럼 0-1, 0-2, 0-3, 0-4, 1-2. 1-3. 1-4, 2-3, 2-4, 3-4 와 같이 확인하면 된다. 코드의 27~28line을 참고해보자. 

 

  그리고 모든 쌍에 대해 각각 GCD를 구해 그 결과를 더해주면 되는데, GCD의 경우 유클리드 호제법을 사용하면 빠르게 구할 수 이다. 유클리드 호제법은 검색해서 원리를 확인하고, 코드로는 gcd() 함수를 확인해보면 된다.

 

코드 : github

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

public class Main {
    private int gcd(int a, int b) {
        int r = -1;
        while (r!=0) {
            r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            long sum = 0;
            for (int i = 0; i < arr.length-1; i++) {
                for (int j = i+1; j < arr.length; j++) {
                    sum += gcd(arr[i], arr[j]);
                }
            }
            sb.append(sum).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}