[BaekJoon] 12852번 1로 만들기 2 (Kotlin) 문제 풀이 [Silver 1]

문제

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

12852번: 1로 만들기 2

 

어떻게 풀 것인가?

처음에는 단순 그리디 방식으로 접근했다.

 

하지만 그렇게 했다가는 시간초과가 발생한다. 문제를 보자. 시간 제한은 0.5초이다.

 

자 이렇게 시간제한이 빡빡하다는 것은 DP로 접근해야함이다.

 

그렇다면 DP 배열에 무엇을 넣어야할까? 점화식 수식을 넣어야한다.

 

그렇다면 점화식은 무엇을 넣어야 하는가? 이 문제에서 원하는 것은 가장 적게 연산하여 1을 도출하는 것이다.

 

그렇다.

 

점화식을 생각해본다면 dp[i] = min(dp[i / 3], dp[i / 2], dp[i - 1]) (i = 1 일때, dp[i] = 0) 

 

풀면서 놓쳤던점

DP는 역씌 어렵다.....

 

이 문제를 통해 얻어갈 것

DP 문제

 

내 코드 

// 백준알고리즘 12852번 1로 만들기 2

data class Node(var value: Int, var process: String)

fun main() = with(System.`in`.bufferedReader()) {
    var num = readLine().toInt()
    val dp = Array(num + 1) { Node(0, "1") }

    for (i in 2..num) {
        var count = Int.MAX_VALUE
        var before = 0
        if (i % 3 == 0) {
            count = dp[i / 3].value
            before = i / 3;
        }
        if (i % 2 == 0) {
            if (count > dp[i / 2].value) {
                count = dp[i / 2].value
                before = i / 2
            }
        }

        if (count > dp[i - 1].value) {
            before = i - 1
        }
        dp[i] = Node(dp[before].value + 1, i.toString() + " " + dp[before].process)
    }
    println(dp[num].value)
    println(dp[num].process)
}

 

참고

X