N개의 최소공배수 (C#)

📌문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

📌제한 사항

arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.

📌입출력 예

arr result
[2,6,8,14] 168
[1,2,3] 6

🔍유클리드 호제법

이 문제에 적용할 공식이며
두 자연수 A, B의 최대 공약수(GCD)를 찾는 알고리즘이다.
GCD를 찾는 이유는 문제에서 제시된 최소공배수(LCM)을 구하기 위해서이며 공식 설명은 생략한다.

• LCM = A x B / (GCD)

💡풀이

• 첫 두 수의 LCM을 구한다.
• for문을 돌며 나머지 수의 LCM을 계속 구한다.

public int solution(int[] arr) 
{
	if (arr.Length == 1) // 길이가 1 이상이라고 했기 때문에 예외를 둔다.
    	return arr[0];
    
    int answer = LCM(arr[0],arr[1]); // 첫 LCM를 구한다.
    
    if (arr.Length == 2) // 길이가 2일 때 첫 LCM을 반환한다.
    	return answer;
    
    for(int i = 2; i < arr.Length; i++) // 길이가 3이상일 때 answer와 arr[i]의 LCM을 구해 answer를 갱신한다.
    	answer = LCM(answer,arr[i]); 
    
    return answer;
}

public void LCM(int a, int b)
{
	int n = a;
    int m = b;
    while (m > 0) // while문을 돌며 GCD n을 구한다.
	{
    	int r = n % m;
    	n = m;
    	m = r;
	}
    return a * b / n; // 주어진 두 자연수 a * b를 GCD n으로 나눠 LCM을 구한다.
}