[백준] [9613] GCD 합 (유클리드) (JAVA)

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

9613번: GCD 합

---

문제

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

입력

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

출력

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

---

※ JAVA 코드 (GCD 합)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        while(t-- > 0){
            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 result = 0;

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

    // 재귀를 통한 최대공약수
    static int recursiveGCD(int a, int b) {
        if(b == 0){
            return a;
        } else {
            return recursiveGCD(b, a % b);
        }
    }
}

---

※ 생각정리 (GCD 합)

최대공약수라는 말을 얼마나 오랜만에 들어보는지 반갑기도 했고 "내가 예전에는 두 수의 최대공약수, 최대공배수를 구할때는 어떻게 구했었지?" 라는 생각을 돌아보게 되었다.

1. 최대공약수에 대한 기억

- 최대공약수를 구할때 가장 먼저 떠올릴 수 있는 방법은 두수의 각각의 약수를 모두 구한 후, 두 약수집합간의 공통 집합을 찾는 것이다.

각 수의 약수를 나열해보면 공통 수중에서 가장 큰 수를 선택할 수 있다.

 

 

그렇다면 이러한 방법이 알고리즘에서 는 어떻게 표현될 수 있을까?

사실 최대공약수에는 재미있는 법칙이 있다.

1) 두수를 나누었을때 나누어떨어지면 작은 수가 최대공약수가 된다.

2) 두수가 나누어떨어지지 않을때에는 큰 수에서 작은 수를 나눈후 이때의 작은 수를 제수 나머지를 피제수로 하여 계속 반복한다. (제수는 나누는 수, 피제수는 나누어지는 수를 뜻한다)

 

예를들어 124와 8의 최대공약수를 구한다고 해보자.

우선 124에서 8을 나누었을때 나머지가 0이라면 1번 법칙에 따라 최대공약수가 8이 되게 된다.

하지만, 나누어지지 않기 때문에 2번 법칙을 따라야한다. 먼저 124 % 8을 하였을때 몫은 15이고 나머지는 4이며 나머지가 0이 아니기 때문에 두 수중 더 작은 수인 8을 제수, 결과로 나오게된 나머지를 피제수로 하여 반복한다.

이어나가면 8 % 4를 하였을때 나머지가 0이기 때문에 결론적으로 124와 8의 최대 공약수는 4이다.

 

1. 재귀함수의 사용

위와 같은 패턴으로 최대공약수를 구할 수 있다는 것을 알았다면 이를 코드로 표현 할 수 있다. 사실 반복문으로도 해결할 수있는 문제지만 패턴이 복잡거나(피보나치) 또는 데이터의 양이 많은 경우가 아니라면 재귀함수를 활용하는 것이 간결하기때문에 재귀함수를 이용했다.

// 재귀를 통한 최대공약수
static int recursiveGCD(int a, int b) {
    if(b == 0){
        return a;
    } else {
        return recursiveGCD(b, a % b);
    }
}

 

위 함수를 보면 되게 간단하다 a, b는 최대 공약수를 구할 두수이며, 피제수가 0이면 a를 호출하고 종료, 아니면 재귀를 반복한다.

 

- 새벽코딩 -