프로그래머스 LV.2 - N개의 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

 

최대 공약술르 구하는 알고리즘으로 유클리드 호제법이라는 것이 있다.

이 알고리즘을 통해 최대 공약수를 구하는 과정을 코드로 나타내면 다음과 같다.

 

int GCD(int a, int b)
{
    int m = max(a, b);
    int n = min(a, b);

    while (m % n != 0)
    {
        int r = m % n;
        m = n;
        n = r;
    }
    return n;
}

 

왜 최대 공약수를 구하냐면,

최대공약수와 최소공배수는 다음과 같은 관계를 만족한다.

이 관계는 아래와 같이 표현될 수 있다.

즉 최소공배수 = 두 수의 곱 / 최대 공약수 식이 성립되는 것이다.

 

왜 이런 관계가 성립하는가?

 

최대 공약수와 최소 공배수가 두 수의 곱을 나누는 이유는

두 수의 중복된 소인수를 고려하기 때문이다.

예를 들어 a와 b를 소인수분해한다고 할 때

GCD(a,b)는 두 수의 공통된 소인수의 최댓값을 포함한다.

반대로 LCM(a,b)는 공통된 소인수를 한 번만 포함한 뒤, 나머지 부분을 결합한 형태이다.

따라서 두 수를 곱하면 공통된 소인수가 두 번 포함되는데,

이를 GCD(a,b)로 나누어줌으로써 중복된 소인수를 제거하여 최소공배수를 얻는 것이다.

 

a = 12, b = 18이라는 가정을 해보자.

그럼 다음과 같은 식이 성립한다.

 

그럼 계속해서 구한 최소 공배수와 다음 인덱스와의 최대 공약수를 구해주고

그걸 기반으로 또 최소 공배수를 받아오는 것을 배열이 끝날 때 까지 반복하면

다음과 같은 코드가 완성된다.

int GCD(int a, int b)
{
    int m = max(a, b);
    int n = min(a, b);

    while (m % n != 0)
    {
        int r = m % n;
        m = n;
        n = r;
    }
    return n;
}

int solution(vector<int> arr) {
    int answer = arr[0];
    int lcm = 0, gcd = 0;

    for (int i = 0; i < arr.size(); i++) {
        gcd = GCD(answer, arr[i]);
        lcm = answer * arr[i] / gcd;
        answer = lcm;
    }

    return answer;
}