백준 2609번 : 최대공약수와 최소공배수

백준 2609번 : 최대공약수와 최소공배수

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int gcd = greatestCommonDivisor(a, b);
        System.out.println(gcd);
        System.out.println(greatestCommonMultiple(a,b, gcd));
    }

    public int greatestCommonDivisor(int a, int b){
        if(b%a==0){
            return a;
        }else{
            return greatestCommonDivisor(b%a, a);
        }
    }

    public int greatestCommonMultiple(int a, int b, int c){
        return a*b/c;
    }
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

처음에 브루트포스로 입력 받은 제일 작은 수부터 서로 나누어 떨어질때의 값을 사용하려고 했었다. 시간 복잡도는 O(N)이다. 근데 입력부분에서 이 둘의 정수는 10000 이하의 자연수라는 점에서 브루투포스로 하다간 큰일날 것 같았다... 그래서 다시 폭풍 서치... 유클리드 알고리즘을 알게되었다. 

 

유클리드 호제법

두 자연수의 최대공약수를 구하는 알고리즘의 하나로 두 자연수의 최대공약수 (A, B) 는 최대공약수 (B, R)와 같다는 것이다.  R은 두 자연수의 mod 계산 값의 결과이다. 그러므로 A = 10, B = 15 라고 했을 경우

10 % 15 = 10

=> 15 % 10 = 5

=> 10 % 5 = 0

이렇게 결과가 0이 될 때 두 번째 항에 있는 값이 최대 공약수다. 

 

최소공배수는 두 자연수의 곱을 최대공약수로 나누어주면 최소공배수다.

10 x 15 = 150 / 5 = 30 (최대공배수)