[Java] 백준 GCD 합

1. 문제분석

모든 쌍의 GCD = 최대공약수를 구하는 문제다.

최대공약수를 구하는 방법은 많다. 이 문제에서는 유클리드 호제법을 사용했다.

 

유클리드 호제법은 다음과 같다.

1. 두개의 수 중, 작은 수 / 큰 수의 나머지를 구한다.

2. 나머지가 0일 때, 현재 작은 수를 return한다.

3. 0이 아니라면 원래 작은 수를 큰 수로, 나머지는 작은 수로 다시 구한다.

 

주의할 점은 구하는 값을 long으로 해야한다.

만약 테스트 케이스 개수가 100개, 값이 999,999라면 int로는 데이터를 표현할 수 없다.

2. 구현

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

public class Main {

    //유클리드 호제법
    //두 수가 주어지고 큰 값을 작은 값으로 나눌때 0이라면 작은 수가 최대공약수
    //아니면 반대로 값을 넣어서 진행
    private static long GCD(int a, int b){
        if(b == 0) return a;
        else return GCD(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        //BufferedReader 로 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        //배열 입력
        int count = Integer.parseInt(br.readLine());

        for (int i = 0; i < count; i++) {
            //값이 크기 때문에 long
            long answer = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] arr = new int[Integer.parseInt(st.nextToken())];

            //데이터 입력
            for (int j = 0; j < arr.length; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }

            //두개의 쌍에서 최대 공약수를 찾음
            for (int j = 0; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    answer += GCD(arr[j], arr[k]);
                }
            }
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
}

데이터를 입력받고 서로 쌍을 찾아가며 구한다.

(0번째, 1번째), (0번째, 2번째) .... (n-1번째, n번째) 처럼 곂치지 않고 하나씩 구해간다.

문제만 이해한다면 어렵지 않게 풀 수 있다.

 

3. 마무리

나는 처음에 서로 곂치는 공약수를 다 구하라는건가 싶어서 모든 최대공약수를 구했다.

Map에 넣어두고 value가 arr의 크기라면 그 수를 전부 더했는데 도통 이해가 안갔다.

문제 이해하는 것도 실력인가보다..