1463 1로만들기 (Kotlin)

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

1463번: 1로 만들기

Dp 문제중 Bottom-Up방식을 사용해서 해결한 문제입니다.

 

Bottom-up 방식이므로 규칙중 가장 나중 규칙인 1로 빼는 계산부터 시작하여 각각 배열에 최대값을 저장해줍니다. 

이후 2로 나누는 경우 3으로 나누는 경우를 각각 생각하여 각 배열에 저장된 값중 최소값을 다시 배열에 저장해주면서 1로 만드는 계산을 해줍니다.

fun main() {
    val n = readLine()!!.toInt()
    val num = IntArray(n+1)
    num[1] = 0
    num[0] = 0
    for(i in 2..n){
        num[i] = num[i - 1] + 1
        if(i%2 == 0) num[i] = Math.min(num[i],num[i / 2] + 1)
        if(i%3 == 0) num[i] = Math.min(num[i],num[i / 3] + 1)
    }
    println(num[n])
}