[백준/코틀린] 1463번: 1로 만들기

링크

1463번: 1로 만들기

풀이

dp[i]: i를 1로 만들기 위한 최소 연산 횟수

n에서 1을 만들기 위한 최소 연산 횟수를 구하기 위해,
1에서 n을 만드는 반대 연산의 최소 횟수를 구하는 방식으로 접근합니다.

즉, dp[i]는 dp[i - 1], dp[i / 2], dp[i / 3] 중 최솟값에 1을 더한 값이 됩니다.

코드

fun main() {
    val n = readln().toInt()
    val dp = MutableList(n + 1) { Int.MAX_VALUE }

    dp[1] = 0
    (1..n).forEach {
        if (it + 1 <= n) dp[it + 1] = minOf(dp[it + 1], dp[it] + 1)
        if (it * 2 <= n) dp[it * 2] = minOf(dp[it * 2], dp[it] + 1)
        if (it * 3 <= n) dp[it * 3] = minOf(dp[it * 3], dp[it] + 1)
    }

    println(dp[n])
}