프로그래머스 2023.06.02 (2Lv 여러 수의 최소공배수 구하기)

문제

---

이론

---

최대공약수(Greatest Common Division) 두 수를 소인수분해를 한 뒤, 두 수의 공통된 소인수를 모두 곱한 것이다.

최소공배수(Least Common Multiple) 두 수를 소인수분해를 한 뒤, 두 수의 모든 소인수를 곱한 것이다.

벤-다이어그램으로 정리하면 아래와 같다.

https://dimenchoi.tistory.com/46 참고

AB = LCM*GCD

 

유클리드 호제법

A를 B로 나눌 때, 나머지를 R이라하면, GCD(A,B) = GCD(B,R) 이다.

예시 : 60과 24를 나눈 몫은 2이고, 나머지는 12이다. 즉, 60 = 24 * 2 + 12 GCD(60, 24) = GCD(24, 12) = 12 이다.

유클리드 호제법을 이용한 알고리즘

• A와 B의 최대 공약수를 구하기 위해서 A를 B로 나눈 나머지 R0을 구한다.
• B를 R0로 나눈 나머지 R1을 구한다.
• R0를 R1으로 나눈 나머지 R2를 구한다.
• 해당 과정을 반복해 어느 한쪽이 나누어떨어질 때까지 반복한다. 이 직전 얻은 나머지가 최대공약수(GCD)이다. (즉, 나머지가 0이면 최대 공약수)

참고 블로그

https://dimenchoi.tistory.com/46

정수론 (1) - 최대공약수, 최소공배수, 유클리드 호제법

 

최소공배수와 최대공약수의 성질 두 정수의 최소공배수는 최대공약수와 다음과 같은 관계를 가진다.

• LCM(a, b) | ab
• LCM(a, b) * GCD(a, b) = ab
• a | LCM(a, b)
• b | LCM(a, b)

이때, 수학기호 “|”는 두 수를 나누었을 때, 나머지가 0인 경우를 의미한다.

 

코드

---

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> arr) {
    int answer = 0;

    int A = 0;
    int B = 0;

    int High = 0;
    int Low = 0;
    int Result = 0;

    int GCD = 0;
    int LCM = 0;

    for (int i = 0; i < arr.size() - 1; ++i)
    {
        if (LCM == 0)
        {
            A = arr[i + 1];
            B = arr[0];
        }
        else
        {
            if (LCM < arr[i + 1])
            {
                A = arr[i + 1];
                B = LCM;
            }
            else
            {
                A = LCM;
                B = arr[i + 1];
            }
        }

        High = A;
        Low = B;

        while (Low != 0)
        {
            Result = High % Low;
            High = Low;
            Low = Result;
        }
        GCD = High;

        LCM = (A * B) / GCD;
    }

    answer = LCM;

    return answer;
}

유클리드 호제법을 이용해 최대공약수를 구한 뒤, 최대공약수와 최소공배수의 성질( GCD(a, b) * LCM(a, b) = a*b)을 이용해 최소공배수를 구해주었다.

실행 결과

---