백준 9613번 GCD합 [JAVA]

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

 

 

 

GCD가 뭔지도 안알려주는 문제설명을 보고 실망하였다

 

구글에 검색해보니 최대공약수였다 ㅎㅎ.. 상식인가?

 

암튼 문제를 요약하자면

 

1. 첫줄에 테스트 케이스 개수를 입력하고 

2. 각줄의 수의 개수 / 수 를 입력한다

3. 입력한 수를 모두 짝을 이루고 짝을 이룬 각 수에서 나오는 GCD의 합을 구하는 문제이다

 

 

알고리즘 설계

 

1.  일단 테스트 케이스 개수만큼 실행될 for문을 만들고

2. 그 for문안에서 각 테스트 케이스마다 수를 입력할수 있는 배열을 만들어주고 수를 입력한다

3. 최대 공약수를 구해주는 GCD 메소드를 만들어주고 

4. 이중 for문을 이용하여 배열안에 담긴 모든 짝을 GCD메소드로 넘겨 각 짝의 최대공약수의 합을 GCDSum이라는

변수에 담는다 그러고 출력해주면 끝이다

->이 문제의 정답률이 낮았던 이유는 이 변수를 int형이 아니라 long형으로 선언해줘야된다는 것이다

int로 선언하면 범위를 벗어나는 값이 들어가는지 틀렸다고 하는데 자세한건 모르겠다 ㅎㅎ

 

 

이 문제의 point는 GCD함수를 어떻게 구현하느냐이다 

처음에 나는 시간초과를 경험했다

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            int[] arr = new int[num];
            long GCDSum = 0;
            for (int j = 0; j < arr.length; j++) {
                arr[j] = sc.nextInt();
            }

            for (int k = 0; k < arr.length - 1; k++) {
                for (int s = k + 1; s < arr.length; s++) {
                    GCDSum += GCD(arr[k], arr[s]);
                }
            }

            System.out.println(GCDSum);
        }
    }
    public static long GCD(int a,int b){
        long GCDSum=0;
        int min;
        if(a>b)
            min=b;
        else
            min=a;
        for(int i=1;i<=min;i++){
            if(a%i==0 && b%i==0)
                GCDSum=i;
        }

        return GCDSum;
    }
}

 

나는 GCD 메소드를 

매개변수로 받은 a,b를 서로 비교하여 작은값을 min으로 할당하고

1부터 min까지 for문을 돌려서 a와 b를 비교하여 최대공약수를 구하려고 했지만 

GCD 메소드를 호출하는 문에는 이미 이중 for문이 있으므로 또하나의 for문은 시간초과를 발생시켰다

 

그래서 GCD 메소드를 새로 구현하였다

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            int[] arr = new int[num];
            long GCDSum = 0;
            for (int j = 0; j < arr.length; j++) {
                arr[j] = sc.nextInt();
            }

            for (int k = 0; k < arr.length - 1; k++) {
                for (int s = k + 1; s < arr.length; s++) {
                    GCDSum += GCD(arr[k], arr[s]);
                }
            }

            System.out.println(GCDSum);
        }
    }
    public static long GCD(int a,int b){
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }
}

 

a와 b를 매개변수로 받고 

큰수를 작은수로 나눈 나머지가 0이 나올떄까지 함수를 재귀호출해주면 0이 아닌수가 최대공약수가 된다는 원리이다 

 

예를 들어 GCD의 매개변수로 20 10이 들어온다면

 

GCD(10,0)을 재귀호출 하고 b=0이므로 a(=10)을 return해주는데 10인 두 수의 최대공약수가 맞다