백준 9613 GCD 합(Java)

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

9613번: GCD 합

---

 

해석 및 팁

 

---

 

이 문제는 입력받은 수들의 gcd의 합을 구하는 문제입니다. 먼저 유클리듯호제법을 사용하여  gcd합수를 만들어준 뒤 숫자를 입력받아 배열에 저장한 후 하나씩 비교하면서 gcd 함수에 넣어서 합을 구하면 됩니다. sum의 범위는 int의 범위를 넘어갈 수도 있으므로 long을 사용해 주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int t = sc.nextInt();
  
    for(int i = 0; i < t; i++) {
      long sum = 0;
      int n = sc.nextInt();
      int[] arr = new int[n];
      
      for(int j = 0; j < n; j++) {
        arr[j] = sc.nextInt();
      }

      for(int j = 0; j < n - 1 ; j++) {
        for(int k = j + 1; k < n; k++) {
          sum += gcd(arr[j], arr[k]);
        }
      }
      
      sb.append(sum+"\n");
    }
    
    System.out.println(sb);
  }

  public static int gcd(int a, int b) {
    if(a % b == 0) return b;
    else return gcd(b, a % b);
  }
}