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

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

코딩테스트 연습 - N개의 최소공배수

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

using namespace std;

int gcd(int a, int b){
    int a1=max(a,b);
    int b1=min(a,b);
    while (b1){
        int c=a1%b1;
        a1=b1;
        b1=c;
    }
    return a1;
}

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

int solution(vector<int> arr) {
    int answer = 0;
    int prev,g,l;
    if (arr.size()==1)
        return arr[0];
    prev=arr[0];
    for (int i=1; i<arr.size(); i++){
        g=gcd(prev, arr[i]);
        l=lcm(g, prev, arr[i]);
        prev=l;
    }
    return l;
}

괜히 복잡하게 풀었다..

 

이 문제의 포인트는 2개 수의 최소공배수를 구해준 다음, 나머지 수와도 최소공배수를 계속 구해주는 방식이다.

다른 분의 풀이를 보니, (구한 최소 공배수, 나머지 수) 해서 바로 최소공배수를 구하는 방식을 취했다.

최소공배수는 두 수의 곱/최대공약수 이렇게 구해지므로, 최소공배수 함수 안에 최대공약수를 구하는 함수를 호출해야 한다. 

최대공약수를 구하는 함수는 유클리드 호제법을 이용한다 (gcd(a,b)==gcd(b, a%b)), a>=b

유클리드 호제법 함수를 재귀로 구현할 수 있다.