[BOJ/백준] 9613 GCD 합

● [문제번호 9613] GCD 합

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

9613번: GCD 합

 

● 알아야 할 것

: 최대공약수를 구하는 방법

 

● 풀이 과정

: 모든 쌍 (2개의 수 조합)의 GCD를 구하면 된다.

 

● 주의 할 것

: 알아차리지 못해 정답을 알고 난 후 허탈했지만 중요한 부분이 있다.

입력으로 주어지는 수가 100만이고,

N개의 수가 2개의 쌍이 되는 횟수는 N * (N-1) / 2 이므로

N의 최댓값(100)인 경우에 대략적인 계산으로

100^2 * 100만 = 100억 이므로

int형 최대 크기(20억)을 넘어간다.

따라서 각 테스트 케이스의 모든 쌍을 저장할 변수는 long long형으로 선언해야한다.

 

● 참고 할 것

: 해당문제의 결과값이 int형을 수학적으로 넘는 과정 풀이하는 링크

https://ldgeao99.tistory.com/298

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 각 테스트 케이스의 수들을 저장할 vector
vector<int> v;
// 테스트 케이스 횟수 T / 각 테스트 케이스의 수 갯수 N
int T, N;
// 각 테스트 케이스의 가능한 모든 상의 GCD의 합     ★
long long result;

// 최대공약수를 구하는 함수
int GCD(int a, int b)
{
    // 두 수 중 작은 값부터
    int gcd = min(a, b);
    
    // 작아지면서
    while(gcd > 1)
    {
        // 공약수가 된다면
        // 그 수가 최대공약수
        if(a % gcd == 0 && b % gcd == 0)
            return gcd;
        gcd--;
    }
    
    // 1이상의 공약수가 없다면 1이 최대공약수
    return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    
    for(int t = 0; t < T; t++)
    {
        cin >> N;
        
        // vector 초기화, 모든 쌍의 GCD의 합 초기화
        v.assign(N, 0);
        result = 0;
        
        // 입력
        for(int n = 0; n < N; n++)
            cin >> v[n];
        
        // 수가 1개인 경우 해당 수 출력
        if(N == 1)
        {
            cout << v[0] << "\n";
            continue;
        }
        
        // 가능한 모든 쌍의 GCD의 합 구하는 과정
        for(int a = 0; a < N - 1; a++)
            for(int b = a + 1; b < N; b++)
                result += GCD(v[a], v[b]);
        
        // 모든 쌍의 GCD의 합 출력
        cout << result << "\n";
        
        // vector 비우기
        v.clear();
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [301 - 수학 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	9613	GCD 합	https://pirateturtle.tistory.com/189
2	17087	숨바꼭질 6	https://pirateturtle.tistory.com/190
3	1373	2진수 8진수	https://pirateturtle.tistory.com/191
4	1212	8진수 2진수	https://pirateturtle.tistory.com/192
5	2089	-2진수	https://pirateturtle.tistory.com/193
6	17103	골드바흐 파티션	https://pirateturtle.tistory.com/194