Boj9613

ㄴ— title: “[백준][9613번] gcd의합” excerpt: “” categories:

• 알고리즘 tags:
• 백준
• 수학 last_modified_at: 2020-07-31T08:06:00-05:00 toc: true toc_sticky: true toc_label: “페이지 주요 목차”

---

문제 URL

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

나의 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        while (size-- > 0) {
            int n = sc.nextInt();
            int[] arr= new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = sc.nextInt();

            long sum = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    sum += gcd(arr[i], arr[j]);
                }
            }
            System.out.println(sum);
        }
    }

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

느낀점

gcd를 합치는 sum의 자료형을 int로 했더니 범위 초과로 오류 발생

따라서 long 타입 변경했더니 해결 하였다. 범위 초과하는지 항상 조심해야겠다.