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

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　최소 공배수의 개념을 유클리드 호제법을 이용하여 구하는 문제다. 백준 최소 공배수 문제의 연장선으로서, 주어진 벡터의 모든 원소를 순회하며 최소 공배수를 구하면 된다.

---

풀이 (1) 유클리드 호제법 구현

#include <vector>
using namespace std;

int gcd(int x, int y)
{
    if (y == 0)
        return x;

    return gcd(y, x % y);
}

int lcm(int x, int y)
{
    return x * y / gcd(x, y);
}

int solution(vector<int> v)
{
    int answer = 1;

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

    return answer;
}

 

풀이 (2) 라이브러리 활용

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

int solution(vector<int> v)
{
    int answer = 1;

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

    return answer;
}