[백준][Kotlin]1850번 최대공약수

해당문제 내 예제 3번을 보면 값이 매우 클 경우 일반 gcd 함수로는 원하는 결과 값을 찾을 수 없습니다.

하지만 문제를 잘 보면 1의 개수들은 입력받은 a와b의 최대 공약수의 길이를 나타냄을 알 수 있습니다.

3,4 의 최대 공약수는 1 이며, 예제 출력을 보면 "1"입니다.

두번째 예시를 보면 3,6의 최대 공약수는 3이며, 예제 출력은 "111"입니다.

그렇다면 입력받은 두 수의 최대공약수 많큼 1을 출력하면 원하는 결과 값이 나옴을 알 수 있습니다.

 

하기는 작성한 코드와 제출 결과 입니다.

 

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()

    var a = st.nextToken().toLong()
    var b = st.nextToken().toLong()

    var result = gcd(a,b).toInt()

    repeat(result){
        bw.append("1")
    }

    bw.flush()
    bw.close()
}

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