N개의 최소공배수

코드

[ 나의 풀이 ]

#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

int solution(vector<int> arr) {
    int answer = 1;
    map<int,int> m;
    /* 각 숫자들이 어떤 수의 곱으로 이루어져 있는지 검사 */
    for(int i=0;i<arr.size();i++)
    {
        map <int,int> temp;
        int n = arr[i];
        int j=2;
        while(n != 1)
        {
            if(n % j == 0){
                temp[j]++;
                n = n/j;
            }else{
                j++;
            }
        }
        /* 약수의 차수만 필요하므로 기존 map 값과 비교! */
        for(auto it = temp.begin();it != temp.end();it++)
        {
            int idx = it->first;
            int value = it->second;
            m[idx] = max(m[idx], value);
        }
    }
    /* 약수의 최대 차수의 곱들로 정답을 산출 */
    for(auto it = m.begin();it != m.end();it++){
        answer *= pow(it->first,it->second);    
    }
    return answer;
}

• 모든 수를 대상으로 최소 공배수를 구하려면 각 약수들의 최대 차수들의 곱이 필요하다고 생각했음
• 그래서 모든 수의 약수를 구했고, 최대 값들만 map에 저장하여 계산했음
• 밑에 풀이가 더 간단하고 똑똑한 풀이!

---

[ 최적 코드 ]

#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;
}

• key point!
  : 앞에 2개씩 차례차례 최소 공배수를 구하면 결국 모든 수의 최소공배수를 구할 수 있음
• 최대공약수를 구하는 GCD와 최소공배수를 구하는 LCM을 만드는 함수는 외워두자!
• 이것은 유클리드 호제법을 재귀로 구현한 것이다