[Kotlin] 백준 1490 : 자리수로 나누기

문제 링크

1490번: 자리수로 나누기

---

---

문제 해설

문제에서 이야기하는 N의 0이 아닌 모든 자리수로 나누어 떨어진다는 말은 곧 N의 0이 아닌 모든 자리수의 최소 공배수로 나누어 떨어진다는 말과 같다. 따라서 가장 먼저 0이 아닌 모든 자리수의 최소 공배수를 구해야 한다.

 

최소 공배수는 최대 공약수를 이용하여 구할 수 있고(코드의 lcm 함수), 최대 공약수는 유클리드 알고리즘을 사용하여 구할 수 있다(코드의 gcd 함수). 최소 공배수를 구했다면 N으로 시작하면서 최소 공배수로 나누어 떨어지는 수를 탐색해야 한다. 이 부분은 N에 10의 거듭제곱을 곱해가면서 반복문으로 나누어 떨어지는지를 확인해나가면 된다.

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine()
    val digits = n.filter { it != '0' }.map { it - '0' }
    var lcm = digits[0]
    for (i in 1..digits.lastIndex) {
        lcm = lcm(lcm, digits[i])
    }
    val num = n.toInt()
    var checkSize = 1L
    while (true) {
        var temp = num * checkSize
        for (i in 0 until checkSize) {
            if (temp % lcm == 0L) {
                println(temp)
                return@with
            }
            temp++
        }
        checkSize *= 10
    }
}

fun lcm(a: Int, b: Int) = a * b / gcd(a, b)

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