N개의 최소 공배수

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

 

📌 최소 공배수 계산 공식

최대 공배수 == 두 수의 곱을 최대 공약수로 나눈 값이다.

int lcm(int x, int y) { return x * y / gcd(x, y); }

 

✅ 문제 풀이 

#include <vector>

using namespace std;

int gcd(int x, int y) { return x % y == 0 ? y : gcd(y , x % y); }
int lcm(int x, int y) { return x * y / gcd(x, y); }

int solution(vector<int> arr) 
{
    int answer = arr[0];
    
    for(int i = 1; i < arr.size(); ++i)
    {
        answer = lcm(answer, arr[i]);
    }
    
    return answer;
}

x, y 두 수의 모듈러 값은 작은 숫자의 최대 공약수와 같다는 성질을 이용해 최대 공약수를 구하는 함수 gcd 정의하였다.

최대 공약수가 구해진다면 최소 공배수는 간단히 x, y 두 수를 곱한 값에 나눠주면 구할 수 있게 된다.

 

 

유클리드 알고리즘