[프로그래머스] 최소공배수 C++

 

풀이

 

두 수의 최대공약수를 구하는 함수 gcd

최대공약수를 사용하여 최소공배수를 구하는 함수 lcm

 

{a, b, c, d, e......} 와 같은 n개의 최소공배수는 어떻게?

 

a, b의 최소공배수 x를 구하고

x와 c의 최소공배수 y를 구하고

y와 d의 최소공배수 z를 구하고..

 

반복

 

 

int gcd(int x, int y) {
	int n;
	while (y!=0) {
		n = x % y;
		x = y;
		y = n;
	}
	return x;
}

int lcm(int x, int y) {
	return x * y / gcd(x, y);
}

int solution(vector<int> arr) {
	int answer = lcm(arr[0], arr[1]);
	for (int i = 2; i < arr.size(); i++) 
		answer = lcm(arr[i], answer);
	return answer;
}