[자바]N개의 최소공배수

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

프로그래머스

유클리드 호제법

유클리드 호제법 증명

이 증명은 B와 R(A를 B로 나눈 나머지)가 공통된 최대공약수(G)를 갖는다는 것을 증명하면 된다.

그래서 B= Gb와 R=G(a-bq)에서 b와 (a-bq)가 서로소임을 보여주면 된다. 

이를 증명하기 위해 두 값이 서로소가 아님을 가정한다. 그 가정은 모순이 생기고, 따라서 b와 (a-bq)가 서로소이다.

그래서 A와 B의 최대공약수는 B와 R의 최대공약수와 같다는 유클리드 호제법이 성립한다.

---

이 유클리드 호제법을 사용해서 N개 숫자의 최소공배수를 구해야한다.

(for문으로 2개의 수끼리 계속 나누면 시간효율성이 좋지 않기 떄문)

이를 위해서는 만약 N이 3이상이면, 2개씩 짝지어가며 최소공배수를 구한다. 

-> 점점 최소공배수를 불려가면, N개 수의 최소공배수를 구할 수 있다.  

 

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        //최소공배수 반환
        //최대공약수를 먼저 구해서, 그걸로 나눈 값들을 모두 곱한다
        if (arr.length ==1) {
            answer=arr[0];
        }
        int g = gcd(arr[0], arr[1]); //최대공약수
        answer = (arr[0]*arr[1])/g;
        
        if (arr.length>2) {
            for (int i=2; i<arr.length; i++) {
                int temp_g = gcd(answer, arr[i]);
                answer = (answer*arr[i])/temp_g;
            }
        }
        
        return answer;
    }
    public static int gcd(int first, int second) {
        int value = first%second;
        if (value==0) {return second;}
        else {return gcd(second,value);} //재귀이기 때문에 gcd()재귀함수를 반환
    }
}