2609 최대공약수와 최소공배수

이번 문제는 효율적인 알고리즘으로 푸는 법도 소개하겠다.
 

https://www.acmicpc.net/problem/2609

 
num1, num2의 최소공배수는 grtDivisor, 최대 공약수는 lstMultiple이라고 하겠다.
우선 간단히, 최소 공배수를 구할 때, 많이들 몫중 가장 큰 값을 반복문으로 순회하면서 구하지 않을까 싶다.
또한 최대 공약수는 "(num1 * num2) / grtDivisor"로 구할 수 있다.
 

import java.util.*;
public class S2609 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num1 = sc.nextInt(), num2 = sc.nextInt();
        int max = Math.max(num1, num2);
        int grtDivisor = 1;

        for(int i = 2; i <= max; i++) {
            if(num1 % i == 0 && num2 % i == 0)
                grtDivisor = i;
        }

        System.out.println(grtDivisor);
        System.out.println(num1 * num2 / grtDivisor);
    }
}

이렇게 해도 나쁘진 않다. 하지만 유클리드 호제법을 이용하면 더 효율적인 알고리즘이 가능하다.
 
유클리드 호재법이란 아래의 코드와 같이, 앞엔 뒤의 숫자를, 뒤엔 두 숫자의 나머지를 뒤의 숫자가 0이 될 때, 앞의 숫자가 최대공약수이다.

static int getGrtDivisor(int num1, int num2) {
    if(num2 == 0) return num1;
    else
        return getGrtDivisor(num2, num1%num2);
}

 

import java.util.*;
public class S2609 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num1 = sc.nextInt(), num2 = sc.nextInt();

        int grtDivisor = getGrtDivisor(num1, num2);
        System.out.println(grtDivisor);
        System.out.println(num1 * num2 / grtDivisor);
    }

    static int getGrtDivisor(int num1, int num2) {
        if(num2 == 0) return num1;
        else
            return getGrtDivisor(num2, num1%num2);
    }
}

 
이 알고리즘은 유클리드를 이용하여 구현하였고 시간 복잡도는 대충 O(logN)이다. 따라서 두 수의 입력 크기가 크면 클수록 더욱 빨라지는 효율적인 알고리즘이다.