Programmers / N개의 최소공배수 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: N개의 최소공배수 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

#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 lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int solution(vector<int> arr) {
    int answer = arr[0];

    for (int i = 1; i < arr.size(); i++)
        answer = lcm(answer, arr[i]);

    return answer;
}

---

※ 알아야 할 것

 

최소공배수는 두 수를 곱한 다음 최대공약수로 나누면 최소공배수가 나온다. 함수 gcd가 최대공약수를 구하고, lcm은 그 최소공배수를 구하기 위해서 두 수를 곱한 값에 최대공약수로 나눴다.

 

최대 공약수를 구하기 위해서 유클리드 호제법을 이용했다.