[Algorithm] Programmers :: N개의 최소공배수

https://programmers.co.kr/learn/courses/30/lessons/12953?language=cpp 

코딩테스트 연습 - N개의 최소공배수

int gcd(int a, int b) // 최대공약수
{
    int maxNum = max(a, b);
    int minNum = min(a, b);
 
    while (maxNum % minNum != 0)
    {
        int temp = maxNum % minNum;
        maxNum = minNum;
        minNum = temp;
    }
 
    return minNum;
}
 
int lcm(int a, int b) // 최소공배수
{
    return a * b / gcd(a, b);
}
 
 
int solution(vector<int> arr) 
{
    // n개의 수의 최소공배수는, 
    // n개의 수들의 배수 중 공통이 되는 가장 작은 수.
    int answer = 1;
 
    for (int i = 0; i < arr.size(); i++)
    {
        answer = lcm(answer, arr[i]);
    }
 
    return answer;
}

 

알고리즘공부 조금이라도 해본사람은 해봤을법한 최소공배수문제다.

n개의 숫자에 대한 최소공배수를 구하는 문제인데, solution 코드를 보면 알겠지만 앞에 두개의 숫자부터 최소공배수를 구하고 그 수 그대로 다음 숫자랑 연산해서 최소공배수 구하면된다. 

최소공배수를 쉽게 구하기위해서 최대공약수를 먼저 구하면 되고, 최대공약수는 유클리드호제법으로 구하면된다.