[백준][Kotlin]1934번 최소공배수

최소공배수 혹은 최대 공약수를 구하는 문제는 유클리드 호제법을 이용하면 쉽게 작성 할 수 있습니다.

예시를 들어 설명 하겠습니다.

a :6

b: 10

라고 가정 하였을 때

gcd 함수를 만듭니다.(일반적으로 최대공약수 혹은 최소공부수 함수를 gcd라고 합니다.)

gcd함수의 내용은 2개의 입력값을 받으며 b가 0일 경우 a를 리턴합니다. (먼저 넣는 값이 크다고 가정)

fun gcd(a: Int, b:Int):Int{
    if(b == 0) {
        return a
    }else return gcd(b,(a%b))
}

이렇게 리턴 받은 값은 최대공약수 가 됩니다.

10,6 -> 6,4 -> 4,2 -> 2,0 (이때 a 큰 수 가 최대 공약수가 됩니다.)

최소공배수는 처음 a와b를 곱한 후 구한 최대공약수로 나누어 주면 구할 수 있습니다.

하기 코드는 백준 1934번 최소공배수 문제에 대한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.sqrt


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()

    repeat(N){
        st = StringTokenizer(br.readLine())
        var a = st.nextToken().toInt()
        var b = st.nextToken().toInt()
        bw.appendLine((a*b/gcd(a,b)).toString())
    }

    bw.flush()
    bw.close()
}

fun gcd(a: Int, b:Int):Int{
    if(b == 0) {
        return a
    }else return gcd(b,(a%b))
}