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

9613. GCD 합

9613번: GCD 합

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

가능한 모든 쌍의 GCD의 합을 구하는 문제.

킹클리드 호제법과 재귀함수를 써서 풀수 있었다.

이러한 알고리즘을 설계했다.

 

짜본 재귀 함수의 코드

int GetGCD(int curIndex, int nextIndex, vector<int> arr, int sum)
{
    // 비교할 값이 없으면 멈춘다
    if (nextIndex >= arr.size())
    {
        return 0;
    }

    int a = arr[curIndex];
    int b = arr[nextIndex];

    // 유클리드 호제법
    while (b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }

    // 각 GCD를 합해서 반환
    return a + GetGCD(curIndex, nextIndex + 1, arr, a);
}

 

재귀 호출

for (int j = 0; j < count - 1; j++)
    answer += GetGCD(j, j + 1, arr);

재미있었던 문제이다. 오랜만에 재귀함수를 써서 더 재밌었다... ㅎㅎ