[백준] 1로만들기

 

https://www.acmicpc.net/problem/1463

 

fun main() = with(Scanner(System.`in`)) {
    val size = nextInt()
    val count = Array<Int>(size + 1) { 0 }

    count[0] = 0
    count[1] = 1
    if (size == 1) {
        return println(0)
    }
    count[2] = 1
    if (size == 2) {
        return println(count[size])
    }
    count[3] = 1
    if (size == 3) {
        return println(count[size])
    }

    for (i in 4 until count.size) {
        count[i] = count[i - 1] + 1

        if (i % 6 == 0) {
            count[i] = min(count[i],count[i / 3] + 1)
            count[i] = min(count[i],count[i / 2] + 1)
        } else if (i % 3 == 0) {
            count[i] = min(count[i],count[i / 3] + 1)
        } else if (i % 2 == 0) {
            count[i] = min(count[i],count[i / 2] + 1)
        } else {
            count[i] = min(count[i],count[i - 1] + 1)
        }
    }
    println(count[size])
}