백준 2609번 최대공약수와 최소공배수(코틀린)

두 수를 나눌 수 있는 수 중 가장 큰 수를 최대공약수라고 한다. 18과 12의 최대공약수는 6이 된다. 

두 수 모두의 배수중 가장 작은 수를 최소공배수라고 한다. 9와 12의 최소공배수는 36이다.

 

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

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

 

이 문제는 최대공약수와 최소공배수를 구하는 문제이다.

최대공약수는 두 수중 가장 작은 값부터 1까지 천천히 반복문을 돌아서 찾는 방법과 유클리드 호제법을 이용해서 찾는 방법 2가지가 있다. 첫번째 방법은 평균적으로 n/2, 최악의 경우 n번 수행하여 시간복잡도 O(n)이 된다. 두번째 방법은 두 수의 최대공약수는 큰 수를 작은수로 나눈 나머지와 작은수의 최대공약수가 같다를 이용하여 한쪽이 0이 될 때까지해서 최대공약수를 구하는 것이다. 이는 평균적으로 log n번, 최악의 경우도 log n번이므로 시간복잡도는 O(log n)이 된다.

 

최소공배수는 두 수를 곱한 수에 최대공약수를 나누면 나온다. 이유는 간단한데, 두 수를 각각 A, B라고 하자.

A = 최대공약수*a로, B = 최대공약수*b로 나타낼 수 있다. 이 두 수를 곱하면 최대공약수*최대공약수*a*b가 되어서 최대공약수가 겹치게 되어 최대공약수로 나누어주면 우리가 원하는 최소공배수인 a*b*최대공약수 가 된다. 

핵심 코드는 아래와 같다.

fun gcd(a: Int, b: Int):Int {
    val maximum = max(a,b)
    val minimum = min(a,b)
    return if(minimum==0){
        max(a,b)
    }else{
        gcd(minimum, maximum%minimum)
    }
}
fun lcm(a: Int, b: Int):Int{
    return (a*b)/gcd(a,b)
}