[프로그래머스] N개의 최소공배수(C++)

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

프로그래머스

최대공약수를 구하는 유명한 알고리즘, 유클리드 호제법을 이용한다.

두 숫자를 큰 수 a, 작은 수 b로 구별하여, 두 수가 나누어떨어질 때까지 작은 수와 나머지를 저장한다.

최소공배수는 두 수의 곱/두 수의 최대공약수로 구할 수 있다.

 

계속 최소공배수를 저장해가며 arr 원소를 방문한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//최대 공약수
int gcd(int a,int b)
{
    int A=max(a,b);
    int B=min(a,b);
    while(B!=0)
    {
        int temp=A%B;
        A=B;
        B=temp;
    }
    return A;
}
//최소 공배수
int lcs(int a,int b)
{
    return (a*b)/gcd(a,b);
}

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