[백준] 9613번 GCD 합 JAVA

 

문제의 포인트는 자료형

시간 복잡도 계산 :  n번의 루프안에 n(n-1)/2  

최악의 경우 100 * 100* 99 /2 = 49500번의 루프를 돈다

 

문제는 출력되는 GCD합의 범위

n(n-1)/2 * 입력되는 수의 최대값 1,000,000-1 (그냥 백만으로 계산)

100 * 99 /2 * 1,000,000 =  49억

int형은 +-21억 으로

long 으로 선언해야된다.

 

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int loop = Integer.parseInt(reader.readLine());
        for(int i=0; i<loop ; i++) {
            String[] input = reader.readLine().split(" ");
            int[] arr = new int[input.length-1];
            int loopCnt = Integer.parseInt(input[0]);
            // 숫자배열로 변
            for(int k=1; k<input.length; k++){
                arr[k-1] = Integer.parseInt(input[k]);
            }
            long ans = 0;

            for(int j=0; j<loopCnt-1; j++) {
                for (int k=j+1; k<loopCnt; k++) {
                    int big = Math.max(arr[j], arr[k]);
                    int small = Math.min(arr[j], arr[k]);
                    ans += getGcd(big, small);
                }
            }
            writer.append(String.valueOf(ans));
            writer.append("\n");
        }
        reader.close();
        writer.flush();
    }

    public static int getGcd(int first, int second) {
        int remain = first %second;
//		재귀
        if(remain!=0) {
            return getGcd(second, remain);
        }else {
            return second;
        }
    }
}