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

1.문제 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

2. 입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

3. 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

4. 포인트

1. 1. 동적프로그래밍을 이용해 풀어야한다.
   2. 점화식을 세울 수 있어야한다 
      1. dp[ i ] = min(dp[ i/3 ] , dp[ i/2 ] , dp[ i-1 ] ) +1 
   3. top-down 과 bottom-up 의 풀이를 생각할 수 있으며 장단점을 알아야한다.

4. 문제 풀이 1 : Top-Down

동적 프로그래밍 문제라는 것을 알았지만 오랜만이라 잘 풀리지 않았다. 

top - down 으로 접근했고  처음 코드는 시간 오류가 났다.

처음 코드의 문제는 메모리제이션을 제대로 활용하지 못했기 때문이다. 다른 풀이를 찾아보고 그에 맞게 고쳐 정답을 맞출 수 있었다.

 

top-down의 메모리제이션 풀이는 두 핵심으로 나뉜다. 

1. dp[ idx ] 가 이미 존재할때 그 값을 리턴하는 것

2. dp[ idx ] 가 존재하지 않을때 그 앞에 값을 조회해서 dp[ idx ]를 채우고 해당 값을 리턴하는 것

 

 

// 첫번째 풀이 (시간초과) : 메모리제이션 잘못 활용

var dp = intArrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {


    var num = readLine().toInt()

    dp = IntArray(num + 1) {
        if (it == 0 || it == 1) 0 else -1
    }
    println(recur(num))

}

fun recur(num: Int): Int {
    if (dp[num] != -1) return dp[num]
    else {
        var min = Int.MAX_VALUE

        if (num % 3 == 0) min = min(recur(num / 3)+1 , min)
        if (num % 2 == 0) min = min(recur(num / 2)+1 , min)
        return min(recur(num - 1) +1 , min)

    }

}

// 두번째 풀이 : 메모리제이션 정확히 구현

var dp = intArrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {


    var num = readLine().toInt()

    dp = IntArray(num + 1) {
        if (it == 0 || it == 1) 0 else -1
    }
    println(recur(num))

}

fun recur(num: Int): Int {
    if (dp[num] != -1) return dp[num]
    else {
        var min = Int.MAX_VALUE

        if (num % 3 == 0) min = min(recur(num / 3) , min)
        if (num % 2 == 0) min = min(recur(num / 2) , min)
        min = min(recur(num - 1), min)

        dp[num] = min+1
        return dp[num]

    }

}

5. 문제 풀이 2 : Bottom-Up

항상 dp 문제는 top-down 방식으로 풀어왔었기에 bottom-up 을 찾아보고 구현했다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {


    var num = readLine().toInt()

    var dp = IntArray(num + 1)

    for (i in 2..num) {
        dp[i] = dp[i - 1] + 1
        if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1)
        if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)
    }
    println(dp[num])
}

 

5. TopDown vs Bottom-Up

개인적으로 TopDown 은 좀 더 직관적인 반면  BottomUp은 그렇지 않은 것 같다.

성능면에서는 BottomUp이 함수 스택이 쌓이지 않으므로 더 좋을 것을 알 수 있었다.

둘 모두 연습하고 DP 문제 풀이시 더 쉬운 방법을 사용함이 좋겠다.