[BOJ-2824][백준 2824] 최대공약수[SILVER-1] [Solved by Kotlin]

문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

입력 및 출력

• 입력: 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

• 출력: 두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

풀이

여러 개의 수를 두 줄에 걸쳐 입력 받고 그 각 줄 마다 입력 받은 수를 모두 곱한다. 곱한 후 나온 두 수의 최대공약수를 구하면 되는 문제이다.

단, 문제에서 주어진 조건인 각 줄의 수의 개수(1~1000), 최대 999,999,999이므로 수를 모두 곱하게 되면 최악의 경우(999,999,999^1000)이기 떄문에 Int(-2^31 ~ 2^31-1), Long(-2^63 ~ 2^63-1) 타입으로는 담을 수 없는 수가 나오므로 BigInteger 클래스를 사용한다.

최대공약수를 구할 때는, 유클리드 호제법(유클리드 알고리즘)을 사용하여 수를 구한다.

코드

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*
import java.math.BigInteger
import kotlin.math.sqrt

val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val list1 = readLine().split(" ").map{it.toBigInteger()}
    val m = readLine().toInt()
    val list2 = readLine().split(" ").map{it.toBigInteger()}
    // 각 수를 구하기 위한 변수 선언
    var mul1 = BigInteger("1")
    var mul2 = BigInteger("1")
    // 입력 받은 수들을 모두 곱함
    for(i in list1) {
        mul1 *= i
    }
    for(i in list2) {
        mul2 *= i
    }

    // 최대공약수 알고리즘 실행
    val gcd = gcd(mul1, mul2).toString()
    // 문제 조건에 따라 9자리가 넘어가면 뒤 9자리만 출력
    when{
        gcd.length > 9 -> {
            bw.write(gcd.takeLast(9))
        }
        else -> {
            bw.write(gcd)
        }
    }

    bw.flush()
    bw.close()
    close()
}

fun gcd(n: BigInteger, m: BigInteger): BigInteger {
    return if (n < m) {
        if (n == BigInteger("0")) m else gcd(n, m % n)
    } else {
        if (m == BigInteger("0")) n else gcd(m, n % m)
    }
}

유클리드 알고리즘

유클리드 알고리즘(유클리드 호제법)은 두 수의 최대공약수를 구하는 알고리즘이다.

알고리즘 진행:

1. 두 수 n, m이 있고 n < m 인 관계이다.
2. m을 n으로 나눈 나머지를 k 라고 할 때, k가 0이게 되면 n이 최대 공약수이다. k가 0이 아니면 n보다 더 큰 수가 m을 나누어 떨어지게 할 수 있으므로 최대공약수가 될 수 없다.
3. 2번을 토대로 k가 0이 아니라면, m을 n값으로 치환하고, n을 k값으로 치환 한 후, 2번 과정을 반복하여 나머지가 0이 될때까지 수행한다.

이렇게 m, n 값을 바꾸어주면서 초기 m 값을 나누어 떨어지게 할 수 있는 값을 찾을 수 있게된다.

BigInteger

Int(-2^31 ~ 2^31-1), Long(-2^63 ~ 2^63-1) 타입으로는 담을 수 없을 경우가 발생 할 수도 있다.
이때 BigInteger 클래스를 사용할 수 있다.
BigInteger 클래스는 내부적으로 문자열 형태로 수가 이루어져 있어 숫자의 범위를 무한하게 지정하여 사용할 수 있다. (물론, 디바이스의 메모리의 영향은 받을 것이다.)

이 문제는 위의 2가지 개념을 조합하여 해결을 하였다.

결과

BigInteger를 사용하다보니 메모리를 꽤 쓴 모습을 볼 수 있다.