[BOJ]9613번: GCD 합(java, c++)

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

9613번: GCD 합

 

 

import java.io.*;
 
public class Main {
    public static void main(String[] args) {
 
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
 
            int iTotalCount = Integer.parseInt(br.readLine());
 
            while (iTotalCount-- > 0) {
                
                String[] arrLine = br.readLine().split(" ");
                int n = Integer.parseInt(arrLine[0]);
                
                int[] arrNums = new int[arrLine.length - 1];
                for(int i = 0; i < arrLine.length - 1; i++) {
                    arrNums[i] =Integer.parseInt(arrLine[i + 1]);
                }
                
                long iGCDSum = 0;
                
                for (int i = 0; i < n; i++) {
                    for (int j = i + 1; j < n; j++) {
                        iGCDSum += (GCD(arrNums[i], arrNums[j]));
                    }
                }
                System.out.println(iGCDSum);
            }
 
            System.out.println(sb.toString());
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static int GCD(int A, int B) {
        if (B == 0) {
            return A;
        } else {
            return GCD(B, A % B);
        }
    }
}

 

c++소스

#include <iostream>
#include <vector>
 
using namespace std;
 
int GCD(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    return GCD(b, a % b);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int cnt;
    cin >> cnt;
    while (cnt--)
    {
        // !! 입력값의 범위, 개수를 고려하면 sum자료형은 long long이 되어야 한다
        long long sum = 0;
        
        // 입력
        int n;
        cin >> n;
        vector<int> input(n);
        for (int i = 0; i < n; i++)
        {
            cin >> input[i];
        }
 
        // 가능한 모든 쌍의 GCD합 구하기
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                sum += GCD(input[i], input[j]);
            }
        }
        cout << sum << '\n';
    }
 
    return 0;
}

 

TIP1

 

GCD합 자료형 주의!!

 

long iGCDSum = 0;

 

문제에서 

각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다.

 

어떤 테스트 케이스의 개수가 100개(max)이고, 입력값이 모두 1000000(max)라면 ?

(100 * 99 / 2)  * 1000000 = 약 45억

 

int형의 최대값인 약 20억을 넘는다

 

 

 

 

TIP2

 

방법 1: 각 케이스의 수를 먼저 배열에 그대로 저장한 후, 나중에 호출할 때 Integer 파싱하기

방법 2: 각 케이스의 수를 배열에 저장할때 Integer 파싱하기

 

방법 2가 더 빨랐다!