N개의 최소공배수

들어가는 말

최소공배수를 구하는 문제이다. 최대공배수는 최소공배수를 알면 된다. 최소공배수는 유클리드 호재법을 사용하는데, 두 수를 나눈 나머지를 이용해서 최소공약수를 구하는 방법이다. 최소공약수, 최소공배수 풀이법만 알면 쉽게 푸는 문제지만 거의 3개월만에 다시 푸는 코딩테스트 연습이라 시간이 좀 걸렸다.

코드 설명

gcd가 유클리드 호재법으로 최소공약수를 구하는 방식이다. 우리가 알고 싶은 최대공배수는 lcm으로 gcd를 호출해서 풀면 된다. 주어지는 수가 여러 개이니 앞에서 구한 최대공배수를 n으로 두고 뒤에 있는 숫자와 비교해서 최종 최소공배수를 구하면 된다.

코드

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b){
    int r;
    while(b != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int lcm(int a, int b){
    return (a*b)/gcd(a, b);
    
}

int solution(vector<int> arr) {
    int n = arr[0];
    
    for(int i=1; i<arr.size(); i++){
        n = lcm(n, arr[i]);
    }
    
    return n;

}