[c++/프로그래머스] N개의 최소공배수*

문제 링크

N개의 최소공배수

풀이

유클리드 호제법 - 최대공약수 구하기

1. 큰 수를 작은 수로 나눈다.
2. 나누는 수를 나머지로 계속 나눈다.
   2-1. 나머지가 0일 경우 나누는 수가 최대공약수

최소공배수 구하기
a와 b의 최소공배수는 a*b을 최대공약수로 나눈 값이다.

숫자 두개씩 묶어 나온 최대공약수와 최소공배수를 다음 값과 묶어 계속 계산하면 된다.

코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int gcdFunc(int A, int B)
{
    int a = max(A,B);
    int b = min(A,B);
    
    int r;
    while(b!=0)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

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