[프로그래머스] N개의 최소공배수과 유클리드호제법

🤷‍♂️ 유클리드 호제법?

기본적인 알고리즘 문제들을 풀 때 최소공배수나 최대공약수를 구하라는 문제들이 나온다.
이 때 일반적으로 가장 쉽게 풀 수 있는 방법이 유클리드 호제법이다!

---

📌 최대공약수

유클리드 호제법을 통해서 최대공약수를 쉽게 구해낼 수 있다!
이 방법의 핵심은

큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될때까지 진행

예를 들어 15와 10의 최대공약수는
15 % 10 = 5
여기서 다시 큰 수는 10이되고 나머지 5가 작은 수가 되서 반복적으로 다시!
10 % 5 = 0 임으로 진행은 종료된다!

---

📌 최소공배수

유클리드 호제법을 통해서 최대공약수를 구했다면 최소공배수를 구하는 문제는 정말 쉽게 해결할 수 있다!

예를 들어 그대로 15와 10이라면 이미 우리가 구한 최대공약수인 5까지 이용해서

식 => a * b / gcd(a,b)
예 => 15 * 10 / 5 = 30

---

💻프로그래머스_N개의 최소공배수

위에서 정리한 내용을 바탕으로 해당 문제를 해결할 수 있다!
해당 문제에서는 주어지는 배열 안에 모든 수들의 최소공배수를 구해야하고
최대 15개가 주어짐으로 해당 알고리즘을 가지고 해결하면 된다.

class Solution {
    public int solution(int[] arr) {
        int cur = arr[0];
        
        for(int i = 1 ;i < arr.length; i++){
            //최대공약수 구하고
            int lcm = getLCM(cur, arr[i]);
            System.out.println(lcm);
            //최대공배수 구하자
            cur = cur * arr[i] / lcm;
            System.out.println(cur);
        }
        return cur;
    }
    
    public int getLCM(int a, int b){
        if(a < b){
            int temp = a;
            a = b;
            b = temp;
        }
        
        //큰 수에서 작은 수 나누기
        if(a%b == 0)
            return b;
        
        return getLCM(b, a%b);
    }
}