[백준 2069] [Kotlin] [유클리드 호제법] 최대공약수와 최소공배수

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

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

 

난이도 : 브론즈 1
태그 : 수학, 정수론, 유클리드 호제법

 

 

---

유클리드 호제법

최소공배수와 최대공약수는 유클리드 호제법을 이용해 간단히 구할 수 있습니다.

 

 

최대 공약수 (GCD, Greatest Common Divisor)

유클리드 호제법은 명시적으로 기록된 가장 오래된 알고리즘으로써,

위키피디아에서는 이 알고리즘을 아래와 같이 설명하고 있습니다.

 

 

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

 

한 번 예시를 들어보겠습니다.

 

2개의 자연수 45, 35 (a, b)이 있습니다.

45을 35으로 나눈 나머지는 10(r) 입니다.

 

35를 10로 나눈 나머지는 5입니다.

 

10을 5로 나눈 나머지는 0입니다.

 

나머지가 0이 될때, 제수(5)가 최대 공약수 입니다.

 

 

최소 공배수 (LCM, Least Common Multiple)

a와 b의 최소 공배수 = a * b / 최대 공약수

a와 b의 최소 공배수는 위에서 구한 최대 공배수를 이용해 구할 수 있습니다.

 

 

이제 이론은 끝났으니, 한번 코드로 작성해 봅시다.

 

---

fun main() {
    val input = readLine()!!.split(" ")
    val n1 = input[0].toInt()
    val n2 = input[1].toInt()

    if (n1 > n2) {
        LCM(n1, n2, GCD(n1, n2))
    } else {
        LCM(n2, n1, GCD(n2, n1))
    }
}

fun GCD(n1: Int, n2: Int): Int {
    return if (n2 == 0) {
        println(n1)
        n1
    } else {
        GCD(n2, n1 % n2)
    }
}

fun LCM(n1: Int, n2: Int, gcd: Int) {
    print(n1 * n2 / gcd)
}

 

GCD (최대공약수)는 재귀함수를 이용해 구할 수 있습니다.

 

매개변수로 받는 n2가 0일때는 n1를 반환하고,

 

그렇지 않을땐 n2, n1 % n2를 매개변수로 다시 호출합니다.

 

 

LCM (최소공배수)는 n1 * n2 / gcd를 이용해 쉽게 구할 수 있습니다.

 

 

---

후기

 

코딩테스트를 하면서, 제가 재귀함수에 좀 약하다는 생각이 들어서

 

이 부분을 보완하고자 재귀함수를 집중적으로 공부하면서 풀었던 문제입니다.

 

코딩을 막 접했을 때 봤던 최대공약수와 최소공배수를 다시 보니 반갑네요.