[백준 9613] GCD 합 - 자바

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

9613번: GCD 합

---

1. 풀이

입력 값들을 받고 입력 값들끼리 반복문을 돌면서 두 개씩 짝을 지어 GCD(최소공배수)를 구해서 다 더해주면 되는 문제입니다.

 

문제는 GCD를 더한 값의 범위입니다.

 

테스트 케이스의 수 (n)가 1 ~ 100이고, 입력으로 주어지는 수는 1 ~ 1000000이다.

 

n개인 수를 2개씩 짝지어 만드는 모든 경우의 수는 n(n-1)/2 이므로, 100*99/2 = 4950이다.

 

만약 각각의 n이 1000000이라면 총 합의 최대 범위는 49억이 된다.

 

이는 int형의 표현 범위를 벗어나므로 자바에서는 long을 써줘야한다.

 

---

2. 코드

import java.util.*;

public class Main {

    public static int GCD(int a, int b){
        if(b == 0)
            return a;
        return GCD(b, a%b);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while(t-- > 0 ){
            long result = 0; // int면 범위 초과.
            int[] nums = new int[101];
            int n = sc.nextInt();

            for(int i = 0; i < n; i++){
                nums[i] = sc.nextInt();
            }

            for(int i = 0; i < n; i++){
                for(int j = i+1; j < n; j++){
                    result+=GCD(nums[i], nums[j]);
                }
            }
            System.out.println(result);
        }

        sc.close();
    }
}