🧮 [프로그래머스] N개의 최소 공배수 (Java) ft.유클리드 호재법

문제

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

프로그래머스

 

문제 이해 && 풀이

해당 문제는 이해력이 필요한 문제라기 보다 최소공배수를 다룰 줄 아는지가 중요한 문제이다.

 

프로그래머스에서는 최대 공약수와 최소 공배수를 다루는 문제가 한번 있었다.

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

프로그래머스

 

하지만 차이점은 두개의 수만을 다루어 문제를 풀기 때문에 N개의 문제에서는 또 다른 풀이 법이 필요하다.

 

최대 공약수란?

공약수란 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻으로 최대공약수는 그중 가장 큰 약수를 뜻한다.

최대공약수는 gcd(a,b)라는 수학 기호가 존재한다. 

 

최소 공배수란?

공배수란 두 수, 혹은 그 이상의 수들이 공통인 배수이다. 최소는 그중 가장 작은 수를 뜻한다.  

최소공배수는 lcm(a,b)라는 수학 기호가 존재한다.

※공식 : 최소 공배수 = 두 수의 곱 / 두 수의 최대 공약수

 

유클리드 호제법

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

이처럼 두 수가 있다면 처음에 그 중 한수로 나누고 나머지를 임시 변수(r)에 저장하고 나누어진 수(a)는 나눈 수 (b)가 되고 나눈 수(b)는 임시변수(r)이 된다. 그리고 b가 0이 아닐때까지 반복하고 0이 된다면 a를 return하게된다. 이때 a는 a, b의 최대공약수가 되는 것이다.

 

소스코드