[자바 :: 최대 공약수/최소 공배수 @유클리드 호제법]

문제 풀이 시나리오

최대 공약수 @유클리드 호제법 
1.r = a%b 라고 할때
2. A,B의 최대 공약수는 b,r 의 최대 공약수와 같음
3. r이 0이 될때 A가 최대 공약수

 

최소 공배수 @유클리드 호제법
1. 최소 공배수는 a*b / (최대 공약수)

2. 주어진 수가 3개 이상이면 A,B의 최소 공배수를 A , C를 B에 저장하고

3. 다시 A,B의 최소 공배수 구하기

 

풀이

import java.util.*;




class Solution {
	//Great Common Demoniator
	public static int GCD(int a, int b) {
		while(b != 0) {
			int r = a%b;
			
			a = b;
			b = r;
		}
		return a;
		
	}
    public static int solution(int[] arr) {
        int gcd = GCD(arr[0], arr[1]);
        int lcd = (arr[0]*arr[1])/gcd;
        
        for(int i = 2; i< arr.length; i++) {
        	//a,b 의 최소공배수와 c 의 최소공배수
        	gcd = GCD(lcd,arr[i]);
        	lcd = (lcd*arr[i])/gcd;
        }
        return lcd;
    }
    public static void main(String[] args) {
    	int[] arr = {1,2,3};
    	System.out.println(solution(arr));
    }
}