[알고리즘 PS] 백준 9613번 GCD 합 자바 문제풀이

문제

해당 포스팅은 백준의 9613번 GCD 합 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이번 문제는 전형적인 GCD 문제였다.

 

유클리드 알고리즘을 모르는 사람에겐 어려운 문제였겠지만, 유클리드 GCD 알고리즘을 알고 있는 사람에게는 입력 처리하는게 더 어려웠을 것 같다.

 

만약 유클리드 알고리즘에 대해서 알지 못한다면 유클리드 알고리즘을 통한 최대 공약수와 최소 공배수에서 학습하는 것을 적극 추천한다.

접근법

배열이 주어진다면, 2중 for 문을 통해서 각각 구할 수 있는 gcd를 모두 구하면 된다.

 

하지만 주의해야할 것이 하나 있다.

 

아마 이 문제가 정답률이 30%인 이유는 출력 자료형을 확인하지 않아서 일것 같다.

주의하자

우선 시간 복잡도를 먼저 봐보자.

 

• 테스트 케이스가 최악의 경우 100개
• tc 안에 GCD 쌍을 만들 수 있는 원소의 개수가 최약의 경우 100개
• 한 원소는 최대 1,000,000 까지.

우선 입력 n에 대한 시간 복잡도는 10,000 번으로 충분히 커버 가능하다.

 

하지만 이들의 합을 구하는 문제로 100개의 원소가 모두 1,000,000 언저리의 수라면?

 

100개의 원소는 2개의 조합을 할 수 있으니 100 C 2 에 100만이라면 49.5억이라는 수가 나오므로 int 최대 범위를 초과한다.

 

그래서 결과로 출력할 값의 자료형을 long으로 지정해야한다.

정답 코드

import java.io.*;

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

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

        while(t-- > 0) {
            String[] inputs = br.readLine().split(" ");

            int n = Integer.parseInt(inputs[0]);

            int[] arr = new int[n];
            long answer = 0;

            for(int i = 0; i < arr.length; i++) {
                arr[i] = Integer.parseInt(inputs[i + 1]);
            }

            for(int i = 0; i < arr.length-1; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    answer += gcd(arr[i], arr[j]);
                }
            }
            bw.write(answer + "\n");

        }
        bw.flush();
        bw.close();
    }

    private static int gcd(int a, int b) {
        while(b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

---

문제 회고

이중 for 문을 만드는데 오랜 시간이 걸린 문제이다.
입력 n 크기 배열을 만들고 해당 라인을 배열 값으로 지정하는데 계속 놓쳤다.
거기다 gcd 알고리즘 자체에서도 b = a % b를 해야할 것을 계속 a = a % b라 해서 시간이 오래 걸렸다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.