[Programmers/프로그래머스 lv2][C++] N개의 최소공배수

문제

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

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

 

문제 내용

입력받은 수들의 최소공배수를 구하면 된다.

 

문제 풀이

기본적으로 최대공약수/최소공배수 구하는 식을 알면 된다.

보통은 2개의 수에 대해서만 최소공배수를 구하지만, 이 문제에서는 최소 공배수 구하는 것을 N-1번 반복하면 된다.

 

코드

#include <string>
#include <vector>

using namespace std;

int calcGCD(int a, int b) { // 반드시 a가 더 크게 입력할 것
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int calcLCM(int a, int b) {
    if (a < b)
        swap(a, b);
    return a / calcGCD(a, b) * b; //overflow 방지를 위해 나누기 먼저 진행
}

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

    return num;
}