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

원본 문제

문제 설명

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

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

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

입력

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

출력

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

테스트 케이스

입력	출력
2	1
10	3

문제 풀이 (KOTLIN)(DP : Bottom-Up)

import kotlin.math.min

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    var dp = IntArray(n + 1)
    for (i in 2..n) {
        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[n])
}

문제 풀이 (KOTLIN)(DP : Top-Down)

import kotlin.math.min

var n = 0
var dp = intArrayOf()

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    dp = IntArray(n + 1) {
        if (it == 0 || it == 1) 0
        else -1
    }
    println(topDown(n))
}

fun topDown(n: Int): Int {
    return if (dp[n] != -1) {
        return dp[n]
    } else {
        var min = Int.MAX_VALUE
        if (n % 3 == 0) min = min(min, topDown(n / 3))
        if (n % 2 == 0) min = min(min, topDown(n / 2))
        min = min(min, topDown(n - 1))
        dp[n] = min + 1
        dp[n]
    }
}

문제 풀이 (SWIFT)

let X = Int(readLine()!)!

var dp = [Int](repeating: 0, count: X + 1)

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

print(dp[X])