[백준 온라인저지]GCD합 - 수학

이번 포스팅 문제는 9613번 문제입니다

문제요약

양의 정수 n개가 주어졌을 때 가능한 모든 쌍의 GCD의 합을 구하는 문제

풀이전략

양의 정수n개가 다음과 같이 {10, 20, 30, 40} 이렇게 주어졌다면 

1. 10과 {20, 30, 40} 의 GCD를 각각 구해서 결과값에 더함
2. 20과 {30, 40} 의 GCD를 각각 구해서 결과값에 더함
3. 30과 {40}의 GCD를 구해서 결과값에 더함

구현하기

package BackJoon.수학;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/9613
 * @author troh
 */
public class _9613_GCD합 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 테스트 횟수
        int c = sc.nextInt();
        
        for(int i=0; i<c; i++) {
            // 입력받을 정수 개수
            int s = sc.nextInt();
            
            // 정수 입력
            int[] arr = new int[s];
            for(int j=0; j<s; j++) {
                arr[j] = sc.nextInt();
            }
            
            // gcd 합 출력
            System.out.println(sumGcd(arr));
        }
    }
    
    private static long sumGcd(int[] arr) {
        long sum = 0;
        for(int i=0; i<arr.length-1; i++) {
            for(int j=i+1; j<arr.length; j++) {
                sum += gcd(arr[i], arr[j]);
            }
        }
        return sum;
    }
    
    private static int gcd(int a, int b) {
        if(b == 0) 
            return a;
        else
            return gcd(b, a%b);
    }
}
 

배운점

자연수 A, B 최소공배수(GCD)를 구하는 알고리즘을 알게되었다.