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

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

프로그래머스

1. 유클리드 호제법을 사용하여 최대공약수, 최소공배수를 구한다. 

2. arr을 내림차순 정렬한다. 

3. for문을 돌리면서 최소공배수를 구한다. 

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

using namespace std;

int gcd(int a, int b) {
    int c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
int lcd(int a, int b) {
    return a * b / gcd(a, b);
}
int solution(vector<int> arr) {
    int answer = 1;

    sort(arr.begin(), arr.end(), greater<>());

    for (int i = 0; i < arr.size(); i++) {
        answer = lcd(arr[i], answer);
    }

    return answer;
}

 

유클리드호제법 정리

https://hello-world-cpp.tistory.com/77

[c/c++/알고리즘]유클리드 호제법, 최대공약수와 최소공배수의 관계