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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

n개의 수에 대하여 최소공배수를 구하는 문제이다.

두 수 A, B의 최소공배수(lcm)을 구하는 공식은 다음과 같다.

lcm = A * B / gcd(A, B) (gcd는 A, B의 최대공약수)

 

모든 수의 최소공배수를 구해야 하므로 이전 수의 최소공배수 결과와 다음 수의 최소공배수를 구해나가면 된다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int gcd(int a, int b) {

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

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

int solution(vector<int> arr) {

    int ans = arr[0];
    for (int i=1; i<arr.size(); i++)
        ans = lcm(ans, arr[i]);
    return ans;
}