[프로그래머스] N개의 최소공배수 / 정수론 / 유클리드 호제법

문제 링크

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

프로그래머스

 

C++ 풀이

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

int getGCD(const int a, const int b) {
    if(b == 0) {
        return a;
    }
    
    return getGCD(b, a%b);
}

int solution(vector<int> arr) {
    
    int answer = 1;
    for(const auto& n : arr) {
        int gcd = getGCD(answer, n);
        answer = answer * n / gcd; 
    }
    
    
    return answer;
}

 

해설

두 수의 최소 공배수는 두 수를 곱하고 최대 공약수로 나누면 된다. 유클리드 호제법으로 최대 공약수를 구할 수 있다. 위 코드에서 getGCD()에서 유클리드 호제법을 구현했다.