[Kotlin] 백준 14715 : 전생했더니 슬라임 연구자였던 건에 대하여 (Easy)

문제 링크 : https://www.acmicpc.net/problem/14715

---

문제 해설

나름 간단한(?) 수학 문제. 별다른 알고리즘이 필요하진 않다.

 

슬라임은 2 이상의 에너지를 갖는 슬라임으로 계속 분할할 수 있다. 분할할 수 있는 슬라임이 존재하지 않을 때까지 슬라임을 분할한다는 것은 모든 슬라임의 에너지가 소수가 된다는 것이고, 모든 슬라임의 에너지가 소수가 되도록 분할한다는 것은 다시 말해 최초의 슬라임을 소인수분해하면 된다는 뜻이 된다.

 

문제에서 구해야 하는 값은 슬라임의 흠집 개수 = 슬라임을 분할한 횟수가 된다.

 

\(K=7200\)인 경우를 생각해보자. \(K\)를 소인수분해하면 \(7200=2\times 2 \times 2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 5\)가 된다.

 

이렇게 소인수분해를 한 항을 다시 \(K\)로 만들어나가는 과정을 보면 아래 그림처럼 된다.

여기서 각 단계마다 흠집이 1개씩 늘어나게 되는데 항의 개수를 절반씩 줄여가야(소수점 이하는 올림) 흠집의 개수를 최소로 할 수 있다.

 

즉 문제의 답은 \(K\)를 소인수분해한 항의 개수를 \(T\)라고 했을 때 \(\lceil\log_2{T}\rceil\)가 된다.

Code

import kotlin.math.ceil
import kotlin.math.log2

fun main() = with(System.`in`.bufferedReader()) {
    var k = readLine().toInt()
    var n = 2
    var count = 0
    while (k != 1) {
        while (k % n == 0) {
            count++
            k /= n
        }
        n++
    }
    println(ceil(log2(count.toDouble())).toInt())
}