[백준] 1463 (1로 만들기)

#1 알고리즘

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

하향식 동적 프로그래밍을 구현해 풀었다.

 

이 문제가 까다로운 이유는, 하향식 동적 프로그래밍에서 캐싱(Caching)을 할 때, 어떤 값을 캐싱해야할 지 난감하다는 것이다. 여러가지 경우들 중에서 최솟값을 골라서 캐싱해야 하는데 그 구현이 처음 문제를 봤을 땐 꽤 복잡해보였다. 나는 ArrayList에 재귀호출의 return값들을 담은 뒤, 해당 ArrayList의 최솟값을 골라 캐싱했다.

 

#2 코드 - 코틀린

val caching = Array(1000001) { -1 }

fun main() {
    val n = readln().toInt()

    caching[1] = 0
    caching[2] = 1
    caching[3] = 1

    println(calculateMin(n))
}

fun calculateMin(n: Int): Int {
    if (caching[n] != -1) {
        return caching[n]
    }

    val cases = ArrayList<Int>()

    // case 1
    if (isDivisible(n, 3)) {
        cases.add(1 + calculateMin(n / 3))
    }

    // case 2
    if (isDivisible(n, 2)) {
        cases.add(1 + calculateMin(n / 2))
    }

    // case 3
    cases.add(1 + calculateMin(n - 1))

    // 캐싱과 리턴
    caching[n] = cases.min()
    return caching[n]
}

fun isDivisible(dividend: Int, divisor: Int): Boolean {
    return dividend % divisor == 0
}