프로그래머스 2단계 - N개의 최소공배수

https://programmers.co.kr/learn/courses/30/lessons/12953?language=cpp 

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

-문제 파악

N개의 정수가 주어지고 이 정수들의 최소공배수를 구하여라

 

- 정답

유클리드 호제법으로 최대공약수를 구하고 최대공약수를 이용해서 최소공배수를 구하였다

(https://dhjkl123.tistory.com/34)

유클리드 호제법은 반드시 기억하도록 하자.

 

#include "bits/stdc++.h"

using namespace std;

int func(int a, int b)
{
    if(a>b)
    {
        if(a%b)
            return func(a%b,b);
        else
            return b;
    }
    else
    {
        if(b%a)
            return func(b%a,a);
        else
            return a;
    }
}

int sol(vector<int> arr)
{
    if(arr.size() == 1)
        return arr[0];
    
    vector<int> vec;
    for(int i = 0 ; i < arr.size()-1 ; i++)
    {
       
        int tmp = func(arr[i],arr[i+1]);
        int a = arr[i]/tmp;
        int b = arr[i+1]/tmp;
        vec.push_back(tmp * a* b);
           
    }
    
    return sol(vec);
}

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

    sort(arr.begin(),arr.end());
    
    answer = sol(arr);

    
    return answer;
}