[Algorithm] 백준온라인저지 9613번(BOJ-9613) GCD합 Java로 문제풀이!! (수학)

---

안녕하세요 Coding-Knowjam입니다.

백준 온라인 저지 9613번 GCD합 문제를 Java로 풀어보겠습니다.

GCD라는 것은 최대공약수를 의미합니다.

그럼 시작하겠습니다~

 

1. 문제 설명

문제를 설명하기에 앞서 아래에 링크를 달아놓았으니 문제를 읽고 와주시길 바랍니다.

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

 

문제에서 요구하는 바는 주어진 n개의 수에서 만들 수 있는 모든 2개의 쌍에서 최대공약수를 구해서 전부 합한 값을 구하는 것입니다.

최대공약수는 유클리드 호제법을 이용해서 쉽게 구할 수 있습니다.

유클리드 호제법을 잘 모르시는 분은 제가 설명한 글이 있으니 아래 링크를 통해서 참고해주시길 바랍니다.

[Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609)

 

n개의 수의 가능한 2개의 모든 쌍을 구하는 방법은 단순합니다.

이중 반복문을 통해서 중복 없이 순차적으로 쌍을 구하면 됩니다.

코드로 바로 보면 더 이해하시기 쉬울 테니 바로 코드로 구현해보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.io.*;

public class BOJ_9613 {

    // 백준온라인저지 9613번 GCD합 Java로 문제풀이
    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());

        // 테스트 케이스 개수만큼 반복
        for (int i = 0; i < t; i++) {
            // 케이스 단위로 결과값 저장할 변수
            long result = 0;
            // 주어진 n개의 수 받기
            String[] info = br.readLine().split(" ");
            int n = Integer.parseInt(info[0]);
            // n개의 수로 가능한 모든 쌍의 개수만큼 반복
            for (int j = 1; j < n; j++) {
                for (int k = j+1; k < n+1; k++) {
                    // 2개의 수 받기
                    int A = Integer.parseInt(info[j]);
                    int B = Integer.parseInt(info[k]);
                    // 최대공약수 구하기
                    int GCD = euclidean(Math.max(A, B), Math.min(A, B));
                    // 구한 최대공약수 결과 값 변수에 저장
                    result += GCD;
                }
            }
            // 테스트 케이스 1개 종료시마다 결과 값 버퍼에 저장
            bw.write(String.valueOf(result));
            bw.newLine();
        }
        // 출력
        bw.flush();
    }

    /**
     * 유클리드 호제법 메서드
     * @param bigNumber : 두개의 수 중 큰 수
     * @param smallNumber : 두개의 수 중 작은 수
     * @return
     * 큰 수를 작은 수로 나눈 나머지가 0이면 작은 수를 리턴
     * 0이 아니면 재귀형태로 다시 메서드 호출하며 파라미터로 작은 수, 나머지를 넘거줌
     */
    static int euclidean(int bigNumber, int smallNumber) {
        // 큰 수를 작은 수로 나눈 나머지를 구함
        int R = bigNumber % smallNumber;
        // 나머지가 0인 경우 작은 수 리턴
        if (R == 0) {
            return smallNumber;
        } else {
            // 나머지가 0이 아닌경우 재귀형태로 자기 자신 호출
            // 파라미터로 작은 수, 나머지를 넘김
            return euclidean(smallNumber, R);
        }
    }
}

작성한 코드의 라인마다 주석을 달아놓았으니 천천히 읽어보시길 바랍니다.

최대공약수를 구하는 법과 가능한 모든 쌍을 구하는 반복문만 구현하면 쉽게 풀 수 있습니다.

감사합니다.

---