[백준: 알고리즘_Java] 9613번_GCD 합

 

<문제>

 

---

<풀이>

 

어제 풀었던 문제에서 최대공약수를 구하는 방법을 알았응께

그 방법을 쓰면 되겄슈.

 

근데 각 테스트 케이스에서 가능한 모든 쌍의 GCD(최대공약수)의 합을 구하는 것잉께

 

반복문을 이용했슈,,

테스트 케이스의 수들을 배열 inpnut 에 넣은 뒤,
예들들어 테스트 케이스의 숫자들이 4개라 하면
input[1] - input[2],input[3],input[4]
input[2] - input[3],input[4]
input[3] - input[4]
의 짝으로 GCD를 구해서 더하면 되는 것이다.

 

 

여기서 주의점은! 테스트 케이스의 수가 100, 입력으로 주어지는 수가 1000000으로 구성되면
GCD의 합들이 int의 범위를 넘어가므로 합을 구하는 변수는 long으로 설정해야한다.

 

 

import java.util.*;

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

        //테스트 케이스 수
        int n = sc.nextInt();

        //테스트 케이스 값 넣을 배열
        int [] input;


        //테스트 케이스 수만큼 반복
        for(int i = 0; i < n; i++) {
            int num = sc.nextInt();

            //GCD 합 초기화
            long total = 0;
            input = new int[num];

            //배열에 값 넣기
            for(int j = 0; j < num; j++) {
                input[j] = sc.nextInt();
            }
            //가능한 모든 쌍의 GCD값을 total에 더하기
            for(int h = 0; h<num-1; h++) {
                for(int g = h+1; g < num; g++) {
                    total += GCD(input[h], input[g]);
                }
            }
            System.out.println(total);

        }


    }
    public static int GCD(int a, int b) {
        while(b != 0) {
            int r = a%b;

            //GCD(a, b) = GCD(b, r)
            a = b;
            b = r;
        }
        return a;
    }
}

 

 

---

<결과>