[Programmers] Lv.2 : N개의 최소공배수

최소공배수를 구하는 방법에는 여러가지가 있지만, 유클리드 호제법으로 최대 공약수를 구한 뒤, 두 수의 곱을 최대 공약수로 나누는 방법이 구현도 간단하고 성능도 적당하다.

유클리드 호제법은 a = bq+r , (a < b, 0 <= r < q) 일 때, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 것이다.
이것을 코드로 구현할 때의 키 포인트는 첫번째, a와 b를 비교할 필요가 없다는 것이고, r이 0이 되면 a의 최대 공약수는 b가 된다는 것이다.
즉 r이 0이 될 때 까지 공식을 반복하면, a와 b의 최대 공약수를 구할 수 있다. 그리고 r은 a를 b로 나눌 때의 나머지로 정의된다.

유클리드 호제법을 구현한 코드는 다음과 같다.

int euc(int a, int b){
	if(a % b == 0) return b;
	return ecu(b, a%b);
}

이렇게 재귀함수로 구현하는 것은 깔끔하지만, 속도가 느리다. 반복문으로 구현하면 다음과 같다.

int ecu(int a, int b){
	while(b!=0){
		int tmp = a;
		a = b;
		b = tmp & b;
	}
	return a;
}

최대 공약수를 구했다면 최소 공배수를 구하는 것은 간단하다. 두 수를 곱한 뒤  구한 최대공약수로 나눠주기만 하면 끝이다.
아래는 전체 코드이다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int arr[], size_t arr_len) {
    int answer = 0;
    for(int i = 0; i < arr_len-1; i++){
        answer = arr[i]*arr[i+1];
        while(arr[i+1]!=0){
            
            int tmp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = tmp % arr[i+1];
        }
    answer=answer/arr[i];
    arr[i+1]=answer;
    }
    answer = arr[arr_len-1];
    return answer;
}