[알고리즘C++] N개의 최소공배수

후이재·2020년 9월 12일
2

오늘의 문제

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

N개의 최소공배수

나의 풀이

#include <string>
#include <vector>

using namespace std;
int GCD(int a, int b){         // 최대공약수
    if(a == 0) return b;
    return GCD(b % a, a);
}
int LCM(int a, int b){         // 최소공배수
    return a * b / GCD(a,b);
}
int solution(vector<int> arr) {
    int answer = 0;
    answer = arr[0];
    for(int i=1;i<arr.size();i++){
        answer = LCM(answer, arr[i]);
    }
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int x, int y) { return x % y == 0 ? y : gcd(y, x % y); }
int lcm(int x, int y) { return x * y / gcd(x, y); }
int solution(vector<int> arr) {
    int answer = arr[0];
    for (int i = 1; i < arr.size(); i++)
        answer = lcm(answer, arr[i]);
    return answer;
}

배울 점

  • 이미 알고있는 함수가 있으니 풀기가 수월
profile
공부를 위한 벨로그

0개의 댓글