프로그래머스 - N 개의 최소공배수

programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

 

최소공배수(LCM) 은 "두 수의 곱 / 두 수의 최대공약수" 로 구한다.

최대공약수(GCD) 는 보통 유클리드 호제법으로 구한다. 

 

- c++

 

#include <algorithm>
#include <vector>
 
using namespace std;
 
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }
int lcm(int a, int b) { return a * b / gcd(a, b); }
 
int solution(vector<int> arr) {
    int answer = arr[0];
    sort(arr.begin(), arr.end());
    for (int i = 1; i < arr.size(); ++i) answer = lcm(answer, arr[i]);
    return answer;
}

 

 

 

 

 

자주 나오는 것들은 차라리 그냥 외우는게 나을듯..