[Level 2] 12. N개의 최소공배수

12. N개의 최소공배수

Algorithm - Level 2

-  풀이

1. 최소공배수를 구하는 알고리즘은 최대 공약수를 이용한다.

-> 유클리드

2. 최대 공약수는 a를 b로 나눠 떨어지면 b가 최대 공약수가 되며, 그렇지 않은 경우 b가 a가 되고 나머지 r이 b가 되어 다시 반복한다.

3. 최대공약수를 이용하여 최소 공배수를 구한다.

-> a*b/(gcd(a,b)

4. N개의 최소공배수를 구하는 것은 한번에 N개를 연산하는 것과 2개씩 연산하여 구하는 결과가 같다.

-> i번째와 i+1번째 원소를 연산하고 그 결과를 i+1에 저장

-> 이를 반복하여 마지막 원소의 값은 N개의 최소공배수 값이 된다.

#include <string>
#include <vector>
 
using namespace std;
 
int gcd(int a, int b){
    while(1){
        int q = a/b;
        int r = a%b;
 
        if(r==0)
            return b;
        a = b;
        b = r;
    }
}
 
int lcm(int a, int b){
    int gcdN = gcd(a, b);
 
    return gcdN * (a/gcdN) * (b/gcdN);
}
 
int solution(vector<int> arr) {
    int answer = 0;
 
    for(int i=0; i<arr.size()-1; i++)
        arr[i+1] = lcm(arr[i], arr[i+1]);
    answer = arr[arr.size()-1];
    
    return answer;
}