[Programmers] N개의 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

---

 

문제 해결 과정

착안

일반적으로 프로그래밍을 통해 최소공배수(least common multiplier, LCM)를 구하기 위해 사용하는 알고리즘은 두 개의 숫자에 대한 최소공배수를 구하는 알고리즘이다. 2 개 이상의 숫자들에 대한 최소공배수는 아래와 같이 pairwise 연산을 통해서 구할 수 있음을 이용하고자 하였다.

 

$$LCM(a, b, c) = LCM( LCM( a, b ), c )$$

 

한편, 최소공배수는 두 수를 곱한 결과를 두 수의 최대공약수(greatest common divisor, GCD)로 나누어 구할 수 있으므로 이를 활용하고자 하였다.

 

구현

$n$ 개의 숫자 $a_1, a_2, ..., a_n$에 대한 최소공배수를 위와 같은 원리로 pairwise 연산을 통해 구하고, 최대공약수를 구하기 위해 유클리드 호제법(Euclidean algorithm)을 활용하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>

using namespace std;

int gcd(int a, int b)
{
	while (b)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	
	return a;
}

int solution(vector<int> arr)
{
	int answer = 1;
	for (int n : arr)
		answer = answer * n / gcd(answer, n);

	return answer;
}

 

실행 결과