[C++] 백준 알고리즘 9613번 (GCD합)

문제

 

 

---

이번에 다뤄볼 문제는 9613번 문제 'GCD 합'입니다.

GCD 합 문제에서 연습해야 하는 key-point는 유클리드 호제법과 재귀함수입니다.

 

유클리드 호제법은 두 양의 정수 또는 정식의 최대공약수를 구하는 방법입니다. 

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘 뜻합니다.

 

2개의 자연수 a, b(a>b)에 대해서 a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.

이 성질에 따라 GCD(a,b) = GCD(b,r) = GCD(r,r`) ... 를 반복하여 GCD(b,r)의 r이 0이되면 그때의 b가 최대공약수가 됩니다.

ex) 

 GCD(24,16) = GCD(16,8) = GCD(8,0) -> 최대공약수: 8

 

이를 하나의 재귀함수로 만들어 놓고 호출해주기만 하면 쉽게 해결할 수 있는 문제입니다.

 

아래 해답 코드를 보면 바로 이해하실 수 있습니다.

---

코드(C++)

 

#include <iostream>
using namespace std;
 
int gcd(int a, int b){
    if (b == 0) return a;
    else return gcd(b, a%b);
}
 
int main(){
    int arr[101][101];
    int sum = 0;
    int a, num;
     
 
    cin >> num;
    for (int i = 1; i <= num; i++){
        cin >> a;
        for (int j = 1; j <= a; j++){
            cin >> arr[i][j];
        }
        for (int j = 1; j <= a-1; j++){
            for (int k = j + 1; k <= a; k++)
            sum += gcd(arr[i][j], arr[i][k]);
        }
        cout << sum << endl;
        sum = 0;
    }
    return 0;
}