81. N개의 최소공배수

 

기본 틀 :

public class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        return answer;
    }
}

 

문제를 보고 사람이 최소공배수를 구하는 방법 처럼 풀고자 시도했다.

 

하지만, 그 과정을 코드로 구현하기에는 아직 내 실력이 부족했다...

(방법이 떠오르지 않음...)

 

그래서 두 수의 최대공약수를 구하는 방법 중 가장 유용한 유클리드 호제법을 이용해 최소공배수를 구해줬다.

 

유클리드 호제법은 

 

두 수의 나머지 연산을 이용해 큰 수에서 작은 수를 나눈 나머지를 구하고

 

작은 수를 큰 수로, 나눈 나머지를 작은 수로 교체하여 다시 반복 계산하고

 

이때, 나눈 나머지가 0이 될 때 작은 수가 최대공약수가 되는 방법이다.

 

이렇게 구해진 최대공약수를 이용해 

 

처음 두 수의 곱을 최대공약수로 나눠주면 최소공배수가 된다.

 

위의 과정을 매개변수로 주어진 arr의 요소들로 차례차례 진행하면

 

arr의 마지막 index에는 모든 요소의 최소공배수가 들어가 있게 된다.

 

using System;
using System.Linq;

public class Solution {
    public int solution(int[] arr) 
    {    
        for(int i = 0; i < arr.Length - 1; i++)
        {
            int big = arr[i + 1], small = arr[i];
            while(arr[i] != 0)
            {
                int temp  = arr[i + 1] % arr[i];
                arr[i + 1] = arr[i];
                arr[i] = temp;
            }
            
            arr[i + 1] = big * small / arr[i + 1]; 
        }
        
        return arr[arr.Length - 1];
    }
}