[백준] JAVA 자바 : GCD 합 (9613번)

---

테스트 케이스의 개수가 주어지고, 그만큼 나올 수 있는 모든 두 쌍으로 만든 GCD의 합을 출력하는 문제이다.

사실 호제법과 static 변수만 잘 사용할 수 있다면 큰 어려움 없이 풀 수 있을 듯?
그런데 굳이 static 변수에 저장 안 해도 그냥 main 클래스에 변수 하나 생성해서 거기에 누적합 하면 더 빠를 것 같긴 한데… 난 static으로 했으니 귀찮으니까 이렇게 하자~ㅋㅋ
그런데 최대 수가 100만이기 때문에 int가 아니라 long으로 선언해줘야 한다!

난 처음에 int로 했다가 3번이나 틀렸다… 뒤늦게 깨달음……ㅋㅋㅋㅋ

여하튼 모든 경우의 수에 대해 GCD를 구해서 static long 변수에 계속해서 누적한 후 마지막에 그걸 출력하면 쉽게 해결할 수 있다.

 

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

public class SumOfGCD {
    static long sum;
    
    public static int stoi(String str) {
        return Integer.parseInt(str);
    }
    
    public static int SumOfGCD(int n1, int n2) {
        if (n1==0 || n2==0) return 0;
        
        // 호제법으로 GCD를 구한다.
        if (n1 % n2 != 0) {
            return SumOfGCD(n2, n1%n2);
        } else {
            return n2;
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int t = stoi(br.readLine());
        for (int i=0; i<t; i++) {
            sum = 0;
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int n = stoi(st.nextToken());
            int[] n_list = new int[n]; // n개 만큼의 배열 생성
            for (int j=0; j<n; j++) { // n만큼 반복
                n_list[j] = stoi(st.nextToken()); // 배열에 수를 할당
            }
            
            // 모든 두 쌍의 경우의 수의 GCD를 구해 static 변수인 sum에 누적.
            for (int j=0; j<n_list.length; j++) {
                for (int k=j+1; k<n_list.length; k++) {
                    sum += SumOfGCD(n_list[j], n_list[k]);
                }
            }
            System.out.println(sum);
        }
        
        br.close();
    }
}

 

로그인

 

 

작성일자: 2023-09-15