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

문제

---

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

풀이

---

최소 공배수를 구하기 위해 ‘유클리드 호제법’을 사용했다. 이는 두 수를 나눈 나머지를 반복하였을 때, 나머지가 0이되면 이 때 마지막으로 나눈 수가 최대 공약수인 것을 활용한 것으로, 이를 배열에 모두 적용, 최대 공배수를 리턴하였다.

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b)
{
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int solution(vector<int> arr) 
{
    int answer = 0;
    int temp_gcd = 0;
    int lcm = 0;

    for (int i = 0; i < arr.size()-1; i++)
    {
        if (i == 0)
        {
            temp_gcd = gcd(arr[i], arr[i + 1]);

            lcm = arr[i] * arr[i + 1] / temp_gcd;
        }

        else
        {
            temp_gcd = gcd(lcm, arr[i + 1]);

            lcm = lcm * arr[i + 1] / temp_gcd;
        }

    }

    answer = lcm;
    
    return answer;
}