[백준] 9613 GCD 합 C++ (기초수학)

📌백준 9613 GCD 합
https://www.acmicpc.net/problem/9613

---

GCD : 최대공약수 Greatest Common Deivisor
LCM : 최소공배수 Least Common Multiple

유클리드 호제법을 이용하여 두 수의 최대공약수를 구한다.
그리고 (두 수의 곱) = (최대공약수) x (최소공배수) 임을 기억하자

탐색 방향
N=3일 때 1, 2 번째
N=4일 때 1, 2, 3 번째
원소와 최대공약수를 구하여 더해준다.

배열의 크기를 입력 받는 length 길이만큼 동적으로 할당해주었고, 마지막에는 delete[]로 동적으로 할당된 배열을 해제했다.

new[]를 썼으면 delete[]로, new를 썼으면 delete로 해제해줘야함
C에서는 malloc과 free를 사용

동적할당 해제해주는 이유 : 메모리 누수 발생 가능, 메모리 접근 위반으로 프로그램이 강제종료될 수 있다.
(메모리 누수 : 프로그램이 종료되기 전에 할당했던 모든 메모리가 해제가 돼야하는데 해제가 안됐을 때 발생하는 문제)

---

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

int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return gcd(b,a%b);
}

int main()
{
    int t, length;
    long long GCD;
    scanf("%d", &t);

    while (t--)
    {
        GCD = 0;
        scanf("%d", &length);
        int *arr = new int[length];
        for (int i = 0; i < length; i++)
        {
            scanf("%d", &arr[i]);
            for (int j = 0; j < i; j++)
            {
                    int tmp = gcd(arr[i], arr[j]);
                    GCD += tmp;
            }
        }
        printf("%lld\n",GCD);
        delete[] arr;
    }
}