[Boj] 백준 C++ #9613 GCD합

최근에 정리한 유클리드 알고리즘을 활용해보기 위해 해당 카테고리의 문제 중 하나인 9613번을 풀어보았다.
유클리드 알고리즘은 최대공약수를 빠르고 쉽게 구할 수 있는 방법 중 하나로 아래 링크로 자세한 내용을 확인할 수 있다.

[알고리즘] 유클리드 알고리즘(유클리드 호제법)

 

---

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

---

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b){
    if(a < b){ //swap(더 큰 수가 a, 작은 수가 b로 가도록 함)
        int tmp = a;
        a = b; b = tmp;
    }
    int r = a % b;
    if (r==0) { // 나머지가 0이면 b를 리턴
        return b;
    }else{ // 그렇지 않으면 b와 r의 최대공약수를 구하기 위해 gcd 호출
        return gcd(b,r);
    } 
}
int main() {
    int t; cin>>t;
    long long ans; // gcd의 합이 int 범위를 초과할 수 있음
    while(t--){ // t번 반복
        ans = 0;
        int n; cin >> n;
        vector<int>arr(n);
        for(int i=0;i<n;i++){ // 입력 받기
            cin >> arr[i];
        }
        for(int i=0;i<n;i++){ //이중 for문을 통해 가능한 쌍을 만들어줌
            for(int j=i+1;j<n;j++){ // j=i+1로 하여 불필요한 쌍(자기 자신, 중복된 쌍)을 배제
                int result = gcd(arr[i],arr[j]); // gcd의 결과를 result에 담음
                ans += result; // ans라는 변수에 담아 gcd의 합을 모음
            }
        }
    cout << ans << endl;
    }
    return 0;
}

이러한 방식으로 구현하였다.
처음에 틀렸습니다! 가 떴는데, 질문하기 게시판을 찾아보니 gcd의 합이 int 범위를 초과할 수 있기 때문이었다. 따라서 ans의 자료형을 long long으로 변경하여 맞았습니다!! 를 받을 수 있었다.

---

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

9613번: GCD 합

 

진짜 오랜만에 알고리즘 문제를 풀었다! 1학기에 배웠던 C++를 종강 이후 사용하지 않았더니 입출력 코드부터 찾아보면서 푸느라 오래 걸렸는데 생각보다 실버네 이거 ..? 더 낮을 줄 알았는데.. 기분은 좋다.