(C/C++) 백준 9613번 - GCD 합

문제 출처: https://www.acmicpc.net/problem/9613

9613번: GCD 합

 

1. 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int gcd(int a, int b) {
    // 최대 공약수 구현
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int main() {
    
    int test,n;
    int arr[101];
    scanf("%d", &test); //test케이스 갯수
 
    for (int i = 0; i < test; i++) {
        scanf("%d", &n); //수의 갯수
 
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[j]); //수를 배열에 넣어주기
        }
        long long sum = 0;
 
        for (int k = 0; k < n; k++) {
            for (int m = k+1; m < n; m++) {
                sum += gcd(arr[k], arr[m]); //배열 전체 반복하면서 gcd합을 구해준다.
            }
        }
        printf("%lld\n", sum);
    }
}

 

2. 해결과정

GCD를 유클리드 호제법을 이용해서 구해주면 나머지는 쉽게 해결할 수 있었다.

1) 입력받은 두개의 자연수 중 큰 값을 a, 작은 값을 b라고 한다.

2) a를 b로 나눈다.

3) a를 b로 나눠서 발생한 나머지를 r이라고 하고, a를 b값에 대입, b에 r값을 대입하여 2번 과정 반복

4) 나머지가 발생하지 않으면 b값이 입력 받은 두 수의 최대 공약수 이다.

 

3. 느낀점

유클리드 호제법을 알면 쉽게 풀리는 문제이다. 이를 재귀를 사용하느냐 아니면 사용하지 않느냐에 따라서도 코드의 길이가 매우 달라지기 때문에 공부할게 점점 많아진다고 생각한다.