N개의 최소공배수/C++

N개의 최소공배수

프로그래머스

풀이 방법

 

최소공배수 = 두 수의 곱 / 최대공약수

 

1. 유클리드 호제법을 통해 최대공약수를 구하는 함수를 작성한다.

2. answer에 arr[0]을 대입한다.

3. 기존에 answer에 담겨있단 값과 arr[i]의 최소공배수를 구한다.

4. 이를 반복후 리턴한다.

#include <string>
#include <vector>

using namespace std;

int GCD(int x, int y) {
    if(!x) return y;
    return GCD(y % x, x);
}

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