[프로그래머스/Level 2] N개의 최소공배수 (C++)

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

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

 

유클리드 알고리즘을 이용해서 최대 공약수를 구한 후, 이를 토대로 최소 공배수를 구하면 된다.

이때 오름차순으로 정렬하여, 작은 것부터 큰 것 순서로 최소 공배수를 구하고, 나온 값을 i+1번째 배열에 저장해주었다.

 

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

int getGCD(int a, int b) {
    while(1) {
        if(b%a == 0)  return a;
        int tmp = b;
        b = a;
        a = tmp % a;
    }
}

int getLCM(int a, int b) {
    return a * b / getGCD(a, b);
}

int solution(vector<int> arr) {
    sort(arr.begin(), arr.end());
    for(int i = 0; i < arr.size() - 1; i++) {
        arr[i + 1] = getLCM(arr[i], arr[i+1]);
    }
    return arr[arr.size() - 1];
}