level 2 - N개의 최소공배수

---

최소 공배수와 최대 공약수를 구할 수 있다면 쉽게 풀 수 있다.

최소공배수(LCM, Least Common Multiple)는 최대공약수(GCD, Greatest Common Divisor)를 이용해서 구할 수 있다.

public int LCM(int x, int y) {
	return x * y / GCD(x, y);
}

최대공약수는 유클리드 호제법을 통한 재귀용법으로 구현할 수 있다.

public int GCD(int x, int y) {
	if (y == 0) {
		return x;
	}
	return GCD(y, x % y);
}

배열에 주어진 수들의 최소 공배수는 배열에 있는 모든 수를 곱하고 공통의 최대공약수를 나누면 된다.

예를 들어 {2, 4, 6, 8}의 공통 최대공약수는 직관적으로 2라는 것을 알 수 있고 식으로 표현하면 2 * 4 * 6 * 8 / (2^3) 이 된다.

이를 식으로 표현하면 아래와 같다.

LCM = (arr[0] * arr[1] * … * arr[n-1]) / GCD^(n-1)

하지만 컴퓨터는 한 번에 하나의 연산만 가능하므로, 두 수의 최소공배수를 구하고 그 결과와 다음 숫자의 최소공배수를 구하는 과정을 반복해야 한다.

answer = arr[0];
answer = answer * arr[1] / GCD (answer, arr[1]);
answer = answer * arr[2] / GCD (answer, arr[2]);
…
answer = answer * arr[n-2] / GCD(answer, arr[n -2]);
answer = answer * arr[n-1] / GCD(answer, arr[n -1]);

이를 반복문으로 구현한 최종 코드는 다음과 같다.

class Solution {
	public int solution (int[] arr) {
		int answer = arr[0];
		for (int i = 1; i < arr.length; i++) {
			answer = LCM(answer, arr[i]);
		}
		return answer;
	}
	
	public int LCM(int x, int y) {
		return x * y / GCD(x, y);
	}
	
	public int GCD(int x, int y) {
		if (y == 0) {
			return x;
		}
		return GCD(y, x % y);
	}
}